కనీస సంపూర్ణ వ్యత్యాసం లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది వినిపించే బ్లూమ్బెర్గ్ SAP ఉబెర్
అర్రే

కనీస సంపూర్ణ వ్యత్యాసం లీట్‌కోడ్ పరిష్కారం మాకు ఒక అందిస్తుంది క్రమబద్ధీకరించనివి అమరిక లేదా కొన్ని పూర్ణాంకాలను కలిగి ఉన్న వెక్టర్. కనీస సంపూర్ణ వ్యత్యాసానికి సమానమైన వ్యత్యాసం ఉన్న అన్ని జతలను మేము కనుగొనవలసి ఉంది. కనీస సంపూర్ణ వ్యత్యాసం అనేది ఇచ్చిన వెక్టర్ లేదా శ్రేణి నుండి సాధ్యమయ్యే అన్ని పూర్ణాంకాలలో ఏదైనా రెండు వేర్వేరు అంశాలను ఎంచుకోవడం ద్వారా సాధించగల సంపూర్ణ వ్యత్యాసం యొక్క కనీస విలువ. కాబట్టి, ద్రావణంలో లోతుగా డైవింగ్ చేయకుండా మొదట కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

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

కనీస సంపూర్ణ వ్యత్యాసం లీట్‌కోడ్ పరిష్కారం

వివరణ: కనీస సంపూర్ణ వ్యత్యాసంతో అలాంటి మూడు జతలు మాత్రమే ఉన్నాయి కాబట్టి. మేము వాటిని సమస్యకు సమాధానంగా తిరిగి ఇస్తాము. ఈ మూడింటికి ఒకే తేడా 1 ఉంది. 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]

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), మేము ఇచ్చిన శ్రేణిని దాటి, మరియు సమయ సంక్లిష్టతను తగ్గించిన హాష్ సెట్‌ను ఉపయోగించాము.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే మేము శ్రేణి యొక్క మూలకాలను హాష్ సెట్‌లో నిల్వ చేస్తాము. స్థల సంక్లిష్టత సరళంగా ఉంటుంది.