کم از کم مطلق فرق لیٹکوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے سنائی دیتی بلومبرگ SAP Uber
لڑی

مسئلہ کم سے کم مطلق فرق لیٹکوڈ حل ہمیں ایک فراہم کرتا ہے غیر ترتیب شدہ صف یا کچھ اشارے پر مشتمل ویکٹر۔ ہمیں تمام جوڑے تلاش کرنے کی ضرورت ہے جن میں کم از کم مطلق فرق کے برابر فرق ہے۔ کم سے کم مطلق فرق مطلق فرق کی کم از کم قیمت ہے جو دیئے ہوئے ویکٹر یا سرنی سے ہر ممکنہ عدد کے درمیان کسی بھی دو مختلف عناصر کو منتخب کرکے حاصل کیا جاسکتا ہے۔ تو ، حل میں گہرا غوطہ لگائے بغیر پہلے کچھ مثالوں پر ایک نظر ڈالیں۔

arr = [4,2,1,3]
[[1,2],[2,3],[3,4]]

کم از کم مطلق فرق لیٹکوڈ حل

وضاحت: چونکہ کم از کم مطلق فرق کے ساتھ صرف تین ایسے ہی جوڑے ہیں۔ ہم انھیں مسئلے کے جواب کے طور پر واپس کردیتے ہیں۔ ان تینوں میں 1 کا فرق ہے۔ 1 کا فرق کم سے کم ممکن فرق ہے۔

arr = [1,3,6,10,15]
[[1,3]]

وضاحت: چونکہ کم سے کم مطلق فرق 2 کے برابر ہے ، اور صرف ایک جوڑے کے عین مطابق ہی حاصل کیا جاسکتا ہے۔ انٹیجرز کا یہ جوڑا جواب کے طور پر لوٹ گیا ہے۔

کم سے کم مطلق فرق لیٹ کوڈ حل کے ل Appro اپروچ

مسئلہ کم سے کم مطلق فرق لیٹ کوڈ حل ، ہم سے پوچھتا ہے کہ انٹیجر کے تمام جوڑے تلاش کریں جو ان کے مابین کم سے کم مطلق فرق کے برابر ہوں۔ ہم پہلے ہی بتا چکے ہیں کہ کم سے کم مطلق فرق کیا ہے۔ لہذا ، اس کو دیکھنے کے بجائے آئیے اس مسئلے کو حل کرنے کے طریقہ پر توجہ دیں۔ لہذا ، سب سے پہلے ، ہمیں کم سے کم مطلق فرق تلاش کرنے کی ضرورت ہے۔ کم سے کم مطلق فرق صرف اس سے ملحقہ عناصر کے درمیان پایا جاسکتا ہے جب ترتیب سے ترتیب دیا جائے۔ مسئلہ نے ہمیں غیر ترتیب شدہ سرنی یا ویکٹر فراہم کیا۔ تو ، پہلے ، ہم صف کو ترتیب دیں۔ اس کے بعد ملحقہ اختلافات پر نظر رکھیں اور جب بھی ہمیں کوئی چھوٹا فرق نظر آئے تو جواب کی تازہ کاری کریں۔

ہم ایک غیر ترتیب شدہ سیٹ یا ہیش سیٹ بھی بناتے ہیں جو ویکٹر سے عدد کو محفوظ کرتا ہے۔ بو ہم صرف صف کو عبور کرتے ہیں اور اس تعداد کو تلاش کرنے کی کوشش کرتے ہیں جس میں کم سے کم مطلق فرق کے برابر فرق ہوتا ہے ، جہاں موجودہ عنصر دونوں میں زیادہ ہوتا ہے۔ اگر ہمیں اپنے ہیش سیٹ میں ایسا عنصر مل جاتا ہے تو ، ہم جوابات میں جوڑی جوڑ دیتے ہیں۔ لیکن اگر ہم ایسا نہیں کرتے ہیں تو ہم صرف آگے بڑھ جاتے ہیں۔

ضابطے

کم از کم مطلق فرق لیٹ کوڈ حل کے لئے C ++ کوڈ

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    int mnDiff = INT_MAX, n = arr.size();
    unordered_set<int> h;
    for(int i=0;i<n-1;i++){
        mnDiff = min(mnDiff, arr[i+1] - arr[i]);
        h.insert(arr[i]);
    }
    h.insert(arr[n-1]);

    vector<vector<int>> l;
    for(int i=0;i<n;i++){
        if(h.count(arr[i]-mnDiff)){
            l.push_back({arr[i]-mnDiff, arr[i]});
        }
    }
    return l;
}

int main(){
    vector<int> sequence = {4, 3, 1, 2};
    vector<vector<int>> output = minimumAbsDifference(sequence);
    for(auto x: output){
        cout<<x[0]<<" "<<x[1]<<endl;
    }
}
1 2
2 3
3 4

کم سے کم مطلق فرق لیٹ کوڈ حل کے لئے جاوا کوڈ

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int mnDiff = Integer.MAX_VALUE, n = arr.length;
        HashSet<Integer> h = new HashSet<Integer>();
        for(int i=0;i<n-1;i++){
            mnDiff = Math.min(mnDiff, arr[i+1] - arr[i]);
            h.add(arr[i]);
        }
        h.add(arr[n-1]);
        
        List<List<Integer>> l = new ArrayList<List<Integer>>();
        for(int i=0;i<n;i++){
            if(h.contains(arr[i]-mnDiff)){
                l.add(new ArrayList<Integer>(Arrays.asList(arr[i]-mnDiff, arr[i])));
            }
        }
        return l;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {4, 3, 1, 2};
    List<List<Integer>> output = minimumAbsDifference(arr);
    for(List<Integer> x: output){
      System.out.println(x);
    }
  }
}
[1, 2]
[2, 3]
[3, 4]

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، چونکہ ہم دیئے گئے صفوں کو عبور کرتے ہیں ، اور ہیش سیٹ استعمال کرتے ہیں جس نے وقت کی پیچیدگی کو کم کردیا ہے۔

خلائی پیچیدگی

O (N) ، کیونکہ ہم سرنی کے عناصر کو ہیش سیٹ میں محفوظ کرتے ہیں۔ خلائی پیچیدگی لکیری ہے۔