ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಕೇಳಬಹುದಾದ ಬ್ಲೂಮ್ಬರ್ಗ್ ಸ್ಯಾಪ್ ಉಬರ್
ಅರೇ

ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಒಂದು ಒದಗಿಸುತ್ತದೆ ವಿಂಗಡಿಸದ ಸರಣಿ ಅಥವಾ ಕೆಲವು ಪೂರ್ಣಾಂಕಗಳನ್ನು ಹೊಂದಿರುವ ವೆಕ್ಟರ್. ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸಕ್ಕೆ ಸಮಾನವಾದ ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಜೋಡಿಗಳನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ. ಕನಿಷ್ಟ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವೆಂದರೆ ಕೊಟ್ಟಿರುವ ವೆಕ್ಟರ್ ಅಥವಾ ರಚನೆಯಿಂದ ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳಲ್ಲಿ ಯಾವುದೇ ಎರಡು ವಿಭಿನ್ನ ಅಂಶಗಳನ್ನು ಎತ್ತಿಕೊಳ್ಳುವ ಮೂಲಕ ಸಾಧಿಸಬಹುದಾದ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸದ ಕನಿಷ್ಠ ಮೌಲ್ಯ. ಆದ್ದರಿಂದ, ದ್ರಾವಣದಲ್ಲಿ ಆಳವಾಗಿ ಧುಮುಕುವುದಿಲ್ಲ ಮೊದಲು ನಾವು ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

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]

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ನಾವು ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುವುದರಿಂದ ಮತ್ತು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಕಡಿಮೆ ಮಾಡಿದ ಹ್ಯಾಶ್ ಸೆಟ್ ಅನ್ನು ಬಳಸಿದ್ದೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ರಚನೆಯ ಅಂಶಗಳನ್ನು ಹ್ಯಾಶ್ ಸೆಟ್ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.