किमान परिपूर्ण फरक लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऐकू येईल असा ब्लूमबर्ग सॅप उबेर
अरे

समस्या किमान भिन्नता लीटकोड सोल्यूशन आम्हाला एक प्रदान करते अनसॉर्ट अॅरे किंवा काही पूर्णांक असलेले वेक्टर. आम्हाला सर्व जोड्या शोधण्याची आवश्यकता आहे ज्यात किमान परिपूर्ण फरकाच्या समान फरक आहे. किमान परिपूर्ण फरक म्हणजे निरपेक्ष फरकाचे किमान मूल्य दिले जाते जे दिलेल्या सदिशातून किंवा अ‍ॅरेमधून सर्व शक्य पूर्णांकांपैकी कोणतीही दोन भिन्न घटक उचलून मिळवता येते. तर, सोल्यूशनमध्ये खोलवर गोता न घेता प्रथम काही उदाहरणे पाहूया.

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

किमान परिपूर्ण फरक लीटकोड सोल्यूशन

स्पष्टीकरणः कमीतकमी परिपूर्ण फरक असलेल्या अशा तीन जोड्या आहेत. आम्ही त्यांना समस्येचे उत्तर म्हणून परत करतो. त्या तिघांमध्येही समान फरक आहे. 1 मधील फरक हा कमीतकमी शक्य फरक आहे.

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

स्पष्टीकरणः किमान परिपूर्ण फरक 2 च्या तुलनेत असल्याने आणि केवळ पूर्णांक जोडणीद्वारे मिळवता येते. पूर्णांकांची ही जोडी उत्तर म्हणून परत केली.

किमान निरपेक्ष फरक लीटकोड सोल्यूशनसाठी दृष्टिकोन

कमीतकमी निरपेक्ष फरक लीटकोड सोल्यूशन ही समस्या आपल्याला पूर्ण संख्या असलेल्या सर्व जोड्या शोधण्यास सांगते ज्यात किमान परिपूर्ण फरकाइतकी फरक असतो. किमान परिपूर्ण फरक काय आहे हे आम्ही आधीच सांगितले आहे. तर, त्याकडे पाहण्याऐवजी समस्या कशा सोडवायच्या यावर लक्ष केंद्रित करूया. तर, सर्व प्रथम, आपल्याला किमान अचूक फरक शोधणे आवश्यक आहे. क्रमवारी लावलेल्या पद्धतीने व्यवस्था केल्यावर किमान अचूक फरक फक्त जवळच्या घटकांमध्येच आढळू शकतो. समस्येने आम्हाला एक अनसोर्टेड अ‍ॅरे किंवा वेक्टर प्रदान केला आहे. प्रथम आपण अ‍ॅरे सॉर्ट करू. त्यानंतर समीप असलेल्या फरकाचा मागोवा ठेवा आणि जेव्हा आम्हाला लहान फरक आढळेल तेव्हा उत्तर अद्यतनित करा.

आम्ही वेक्टरमधून पूर्णांक संग्रहित न केलेला क्रमित सेट किंवा हॅश सेट देखील तयार करतो. धनुष्य आम्ही केवळ अ‍ॅरेवरुन जातो आणि मिळवलेल्या किमान परिपूर्ण फरकाइतकी फरक असलेली संख्या शोधण्याचा प्रयत्न करतो, जेथे वर्तमान घटक दोनपेक्षा मोठा आहे. आमच्या हॅश सेटमध्ये आपल्याला एखादा घटक आढळल्यास, आम्ही उत्तरांमध्ये जोड जोडू. परंतु जर आपण तसे केले नाही तर आपण पुढे जाऊ.

कोड

किमान अचूक फरक लीटकोड सोल्यूशनसाठी सी ++ कोड

#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]

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), आम्ही दिलेली अ‍ॅरे ओलांडत असल्याने, आणि एक हॅश सेट वापरला आहे ज्याने वेळेची जटिलता कमी केली आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण आपण अ‍ॅरेचे घटक हॅश सेट मध्ये संचित करतो. जागेची जटिलता रेखीय आहे.