Minimum Mütləq Fərq Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Audible Bloomberg SAP Über
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 39

Problem Minimum Mütləq Fərq Leetcode Həlli bizə təmin edir çeşidlənməmiş array və ya bəzi tam ədədi ehtiva edən vektor. Fərdi minimum mütləq fərqə bərabər olan bütün cütləri tapmağımız tələb olunur. Minimum mütləq fərq, verilən vektordan və ya massivdən bütün mümkün tam ədədlər arasında hər hansı iki fərqli element götürərək əldə edilə bilən mütləq fərqin minimum dəyəridir. Beləliklə, həll yoluna dərindən girmədən əvvəl bir neçə nümunəyə nəzər salaq.

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

Minimum Mütləq Fərq Leetcode HəlliPin

İzahat: Minimum mütləq fərqi olan yalnız üç belə cütlük olduğundan. Problemin cavabı olaraq onları qaytarırıq. Hər üçü də eyni 1 fərqinə sahibdirlər. 1 fərqi mümkün olan ən kiçik fərqdir.

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

İzahat: Minimum mütləq fərq 2-yə bərabər olduğundan və yalnız bir cüt ədədi əldə etmək olar. Bu cüt tam cavab olaraq geri qaytarılır.

Minimum Mütləq Fərqlilik Leetcode Çözümünə yanaşma

Minimum Mütləq Fərq Leetcode Solution problemi, aralarındakı fərqi minimum mütləq fərqə bərabər olan bütün cüt ədədləri tapmağımızı xahiş edir. Minimum mütləq fərqin nə qədər olduğunu əvvəldən bildirmişdik. Beləliklə, buna baxmaq əvəzinə problemi necə həll edəcəyimizə diqqət yetirək. Beləliklə, ilk növbədə minimum mütləq fərqi tapmaq lazımdır. Minimum mütləq fərq, sıralanmış qaydada düzəldildikdə yalnız bitişik elementlər arasında tapıla bilər. Problem bizə çeşidlənməmiş bir sıra və ya vektor təqdim etdi. Beləliklə, əvvəlcə serialı sıralayırıq. Sonra bitişik fərqləri izləyin və daha kiçik bir fərq tapdıqda cavabı yeniləyin.

Həm də vektordan tam ədədləri saxlayan sıralanmamış dəst və ya qarışıq dəsti yaradırıq. Yay biz yalnız serialın üstündən keçirik və cari elementin ikisinin böyüyü olduğu minimum minimum mütləq fərqə bərabər bir fərqi olan sayını tapmağa çalışırıq. Haş dəstimizdə belə bir element tapırıqsa, cavabdakı cütü əlavə edirik. lakin etməsək, sadəcə irəliləyirik.

Kodu

Minimum Mütləq Fərqlilik Leetcode Həlli üçün C ++ kodu

#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

Minimum Mütləq Fərq Leetcode Çözümü üçün Java kodu

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]

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), bəri verilmiş massivi keçdiyimizdən və zamanın mürəkkəbliyini azaldan bir hash setindən istifadə etdik.

Kosmik Mürəkkəblik

O (N), çünki serialın elementlərini hash setində saxlayırıq. Məkan mürəkkəbliyi xətti xarakter daşıyır.

Şərh yaz

Translate »
1