न्यूनतम पूर्ण भिन्नता लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अयोग्य ब्लूमबर्ग SAP Uber
एरे

समस्या न्यूनतम पूर्ण भिन्नता लेटकोड समाधानले हामीलाई एक प्रदान गर्दछ क्रमबद्ध array वा भेक्टरले केहि पूर्णांकहरू समावेश गर्दछ। हामीले सबै जोडीहरू पत्ता लगाउन आवश्यक पर्दछ जुन न्यूनतम निरपेक्ष भिन्नताको बराबर भिन्नता छ। न्यूनतम निरपेक्ष भिन्नता निरपेक्ष भिन्नताको न्यूनतम मान हो जुन दिइएको भेक्टर वा एर्रेबाट सबै सम्भावित पूर्ण संख्या बीच कुनै दुई भिन्न तत्वहरू उठाएर प्राप्त गर्न सकिन्छ। त्यसोभए, समाधानमा गहिरो डाइiving नगरी हामी केही उदाहरणहरू हेरौं।

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

न्यूनतम पूर्ण भिन्नता लेटकोड समाधान

स्पष्टीकरण: त्यहाँ न्यूनतम पूर्ण भिन्नता संग केवल तीन त्यस्तै जोडीहरू छन्। हामी तिनीहरूलाई समस्याको उत्तरको रूपमा फर्काउँछौं। ती सबै तीनमा समान फरक छ। १ को फरक कमतम सम्भव भिन्नता हो।

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

स्पष्टीकरण: किनकि न्यूनतम निरपेक्ष फरक २ बराबर हो, र पूर्णांकको एक जोडीले मात्र प्राप्त गर्न सक्छ। पूर्णांकको यो जोडी उत्तरको रूपमा फर्काइएको छ।

न्यूनतम पूर्ण भिन्नता लेटकोड समाधानको लागि दृष्टिकोण

समस्या न्यूनतम पूर्ण भिन्नता लेटकोड समाधान, हामीलाई पूर्णांकको सबै जोडीहरू भेट्टाउन सोध्छ जुन न्यूनतम निरपेक्ष भिन्नताको बराबर बीचको भिन्नता हुन्छ। हामीले पहिले नै बताइसकेका छौं कि न्यूनतम निरपेक्ष भिन्नता के हो। त्यसोभए यसमा हेर्नुको सट्टा समस्या समाधान गर्ने समाधानमा ध्यान केन्द्रित गरौं। त्यसो भए सबैभन्दा पहिले, हामीले न्यूनतम निरपेक्ष भिन्नता फेला पार्न आवश्यक छ। न्यूनतम निरपेक्ष भिन्नता केवल क्रमबद्ध ढ .्गले व्यवस्थित हुँदा आसन्न तत्त्वहरू बीच मात्र फेला पार्न सकिन्छ। समस्याले हामीलाई एक क्रमबद्ध एर्रे वा भेक्टरको साथ प्रदान गरेको छ। त्यसो भए, पहिले हामी एरे क्रमबद्ध गर्छौं। त्यसो भए नजिकको भिन्नताहरूको ट्र्याक राख्नुहोस् र जवाफलाई अद्यावधिक गर्नुहोस् हामी जहिले पनि सानो फरक पाउँछौं।

हामी एक अनअर्डर गरिएको सेट वा ह्यास सेट पनि बनाउँदछौं जुन भेक्टरबाट इन्टिजरहरू भण्डार गर्दछ। बोइ हामी एर्रेमा मात्र पार गर्छौं र संख्या प्राप्त गर्ने न्यूनतम निरपेक्ष भिन्नता बराबरको भिन्नता भएको पत्ता लगाउने कोशिस गर्छौं, जहाँ वर्तमान तत्व दुईको ठूलो छ। यदि हामीले हाम्रो ह्याश सेटमा त्यस्तो तत्व फेला पार्‍यौं भने, हामी जोडीलाई उत्तरमा थप्दछौं। तर यदि हामी गर्दैनौं भने हामी केवल अगाडि बढ्छौं।

कोड

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), किनभने हामी एर्रेको एलिमेन्ट्स ह्यास सेटमा राख्छौं। ठाउँ जटिलता रैखिक छ।