최소 절대 차 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 들리는 블룸버그 게시물에서 SAP 동네 짱
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 40

최소 절대 차이 Leetcode 솔루션의 문제는 우리에게 분류되지 않은 정렬 또는 일부 정수를 포함하는 벡터. 우리는 최소 절대 차이와 동일한 차이를 갖는 모든 쌍을 찾아야합니다. 최소 절대 차이는 주어진 벡터 또는 배열에서 가능한 모든 정수 중에서 두 개의 다른 요소를 선택하여 얻을 수있는 절대 차이의 최소값입니다. 따라서 솔루션을 자세히 살펴 보지 않고 먼저 몇 가지 예를 살펴 보겠습니다.

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

최소 절대 차 Leetcode 솔루션

설명 : 절대 차이가 최소 인 이러한 쌍이 세 개뿐이기 때문입니다. 우리는 그것들을 문제에 대한 답으로 반환합니다. 세 가지 모두 1의 차이가 동일합니다. 1의 차이는 가능한 가장 작은 차이입니다.

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

설명 : 최소 절대 차이가 2와 같기 때문에 한 쌍의 정수로만 얻을 수 있습니다. 이 정수 쌍이 답으로 반환됩니다.

최소 절대 차이 Leetcode 솔루션에 대한 접근 방식

문제 최소 절대 차이 Leetcode 솔루션은 최소 절대 차이와 동일한 차이를 갖는 모든 정수 쌍을 찾도록 요청합니다. 우리는 최소 절대 차이가 무엇인지 이미 언급했습니다. 그래서 그것을 보는 대신 문제를 해결하는 방법에 집중합시다. 따라서 우선 최소 절대 차이를 찾아야합니다. 최소 절대 차이는 정렬 된 방식으로 배열 될 때 인접한 요소 사이에서만 찾을 수 있습니다. 문제는 정렬되지 않은 배열 또는 벡터를 제공했습니다. 그래서 먼저 배열을 정렬합니다. 그런 다음 인접한 차이를 추적하고 더 작은 차이를 찾을 때마다 답변을 업데이트하십시오.

또한 벡터의 정수를 저장하는 순서가 지정되지 않은 집합 또는 해시 집합을 만듭니다. 우리는 배열을 가로 질러서 얻은 최소 절대 차이와 동일한 차이를 갖는 숫자를 찾으려고합니다. 여기서 현재 요소는 둘 중 더 큰 것입니다. 해시 세트에서 그러한 요소를 찾으면 답변에 쌍을 추가합니다. 하지만 그렇지 않다면 우리는 앞으로 나아갈뿐입니다.

암호

최소 절대 차 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]

복잡성 분석

시간 복잡성

의 위에), 주어진 배열을 순회하고 시간 복잡성을 줄인 해시 세트를 사용했기 때문입니다.

공간 복잡성

의 위에), 배열의 요소를 해시 세트에 저장하기 때문입니다. 공간 복잡성은 선형입니다.

코멘트를 남겨

Translate »
1