Leetcode чечиминин минималдуу абсолюттук айырмасы


Кыйынчылык деңгээли жеңил
Көп суралган угула Bloomberg SAP Uber
согуштук тизме

Маселе минималдуу абсолюттук айырмачылыкты Leetcode Solution бизге берет сорттолгон эмес согуштук тизме же кээ бир бүтүн сандарды камтыган вектор. Айырмасы бар минималдуу абсолюттук айырмага барабар болгон бардык түгөйлөрдү табышыбыз керек. Минималдуу абсолюттук айырмачылык - берилген вектордон же массивден мүмкүн болгон бүтүн сандардын арасынан эки башка элементтерди алуу менен жетишилген абсолюттук айырманын минималдуу мааниси. Ошентип, чечимге терең сүңгүп кирбей туруп, алгач бир нече мисалдарды карап көрөлү.

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 Solution үчүн минималдуу абсолюттук айырмачылыктын коду

#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), анткени биз массивдин элементтерин таштанды топтомунда сактайбыз. Космостун татаалдыгы сызыктуу.