Leetcode-ийн хамгийн бага үнэмлэхүй ялгаа


Хэцүү байдлын түвшин Easy
Байнга асуудаг Дуу авиа Bloomberg SAP Uber
Array

Асуудлын хамгийн бага үнэмлэхүй ялгаа Leetcode шийдэл нь бидэнд ангилаагүй массив эсвэл бүхэл тоонуудыг агуулсан вектор. Хамгийн бага үнэмлэхүй зөрүүтэй тэнцүү зөрүүтэй бүх хосыг олох шаардлагатай байна. Хамгийн бага үнэмлэхүй ялгаа гэдэг нь өгөгдсөн вектор эсвэл массиваас бүх боломжит бүхэл тоонуудын хооронд ямар ч хоёр өөр элементийг сонгон авч болох үнэмлэхүй зөрүүний хамгийн бага утгыг хэлнэ. Тиймээс шийдэлд гүн гүнзгий орохгүйгээр эхлээд хэдэн жишээг авч үзье.

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

Leetcode-ийн хамгийн бага үнэмлэхүй ялгаа

Тайлбар: Хамгийн бага үнэмлэхүй ялгаа бүхий ийм гурван хос л байдаг тул. Бид тэдгээрийг асуудлын хариу болгон буцааж өгдөг. Тэд гурвуулаа ижил зөрүүтэй байна. 1-ийн ялгаа нь боломжит хамгийн бага зөрүү юм.

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

Тайлбар: Хамгийн бага үнэмлэхүй ялгаа нь 2-той тэнцүү тул зөвхөн нэг хос бүхэл тоонуудаар хүрч болно. Энэ хос бүхэл тоог хариулт болгон буцаана.

Хамгийн бага үнэмлэхүй ялгаа бүхий Leetcode шийдлийн арга

Leetcode Solution-ийн хамгийн бага үнэмлэхүй ялгаа гэдэг нь тэдгээрийн хоорондох ялгаа бүхий бүх хос тоонуудыг хамгийн бага үнэмлэхүй зөрүүтэй тэнцүү хэмжээгээр олохыг биднээс хүсдэг. Хамгийн бага үнэмлэхүй ялгаа гэж бид аль хэдийн мэдэгдсэн байсан. Тиймээс үүнийг харахын оронд асуудлыг хэрхэн шийдвэрлэх вэ гэдэгт анхаарлаа хандуулъя. Тиймээс, хамгийн түрүүнд хамгийн бага үнэмлэхүй ялгааг олох хэрэгтэй. Хамгийн бага үнэмлэхүй ялгааг эрэмбэлсэн байдлаар байрлуулахдаа зэргэлдээх элементүүдийн хооронд л олж болно. Асуудал нь бидэнд ангилагдаагүй массив эсвэл векторыг өгсөн. Тиймээс, эхлээд массивыг ангилах болно. Дараа нь зэргэлдээх ялгааг тэмдэглэж, бага ялгаа олох бүрт хариултыг нь шинэчилж байгаарай.

Бид мөн вектороос бүхэл тоонуудыг хадгалах захиалгагүй олонлог эсвэл хэш багц үүсгэдэг. Нум бид массивыг дайран өнгөрч, хамгийн бага үнэмлэхүй ялгаатай тэнцүү зөрүүтэй тоог олохыг хичээгээрэй. Хэрэв бид ийм элементийг хэш багц дээрээ олсон бол хариултанд хосыг нэмнэ. гэхдээ хэрэв үгүй ​​бол бид зүгээр л урагшлах болно.

код

Хамгийн бага үнэмлэхүй ялгааны Leetcode шийдлийн 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

Хамгийн бага үнэмлэхүй ялгааны Leetcode шийдлийн Java код

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), Учир нь бид массивын элементүүдийг хэш багцад хадгалдаг. Сансрын нарийн төвөгтэй байдал нь шугаман хэлбэртэй байдаг.