අවම නිරපේක්ෂ වෙනස ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ සවන් දෙන්න බ්ලූම්බර්ග් SAP Uber
අරා

ගැටළුව අවම නිරපේක්ෂ වෙනස ලීට්කෝඩ් විසඳුම අපට සපයයි වර්ගීකරණය නොකළ අරාව හෝ නිඛිල කිහිපයක් අඩංගු දෛශිකය. අවම නිරපේක්ෂ වෙනසකට සමාන වෙනසක් ඇති සියලුම යුගල සොයා ගැනීමට අපට අවශ්‍ය වේ. අවම නිරපේක්ෂ වෙනස යනු දී ඇති දෛශිකයෙන් හෝ අරාවෙන් ලබා ගත හැකි සියලු පූර්ණ සංඛ්‍යා අතර ඕනෑම වෙනස් මූලද්‍රව්‍ය දෙකක් තෝරා ගැනීමෙන් ලබා ගත හැකි නිරපේක්ෂ වෙනසෙහි අවම අගයයි. එබැවින්, විසඳුමට ගැඹුරට කිමිදීමකින් තොරව පළමුව උදාහරණ කිහිපයක් දෙස බලමු.

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]

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), අපි ලබා දී ඇති අරාව හරහා ගමන් කරන අතර, කාල සංකීර්ණතාව අඩු කළ හැෂ් කට්ටලයක් භාවිතා කර ඇති නිසා.

අභ්‍යවකාශ සංකීර්ණතාව

මත), මොකද අපි අරාවෙහි මූලද්‍රව්‍ය හැෂ් කට්ටලයේ ගබඩා කරනවා. අවකාශයේ සංකීර්ණතාව රේඛීය වේ.