두 배열 사이의 거리 값 찾기 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 동네 짱
배열

문제는 둘 사이의 거리 값 찾기 배열 Leetcode Solution은 arr1과 arr2의 두 가지 배열을 제공합니다. 두 배열과 함께 정수 n이 제공됩니다. 그런 다음 문제는 주어진 두 배열 사이의 상대적 거리를 찾도록 요청합니다. 상대 거리는 주어진 정수 d보다 작거나 같은 최소 절대 차이를 갖는 두 번째 배열에 요소가없는 첫 번째 배열의 요소 수로 정의됩니다. 따라서 항상 솔루션에 깊이 들어가기 전에 먼저 몇 가지 예를 살펴보아야합니다.두 배열 사이의 거리 값 찾기 Leetcode 솔루션

arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
2

설명 : 첫 번째 배열에서 각 요소를 하나씩 선택하여 출력을 확인합니다. 첫 번째 요소 4의 경우 두 번째 배열에는 최소 절대 차이가 2 인 해당 요소가 없습니다. 5도 마찬가지입니다. 그러나 마지막 요소 인 8을 보면 두 번째 배열에 같은 값을 가진 요소가 있습니다. 따라서 8은 답으로 간주되지 않습니다. 따라서 대답은 첫 번째 배열의 처음 2 개 요소 때문에 2가됩니다.

두 배열 사이의 거리 값을 찾기위한 무차별 대입 접근 방식 Leetcode 솔루션

문제에 대한 무차별 대입 솔루션은 고유 한 쌍을 선택하는 두 어레이 모두에서 반복됩니다. 그런 다음이 고유 쌍은 그 차이가 주어진 정수 'd'보다 작은 지 확인합니다. 차이가 d보다 작 으면 요소에 플래그를 지정합니다. 플래그가 지정된 요소는 계산하지 않으며 나머지 요소의 개수는 답으로 반환됩니다. 해결책은 매우 간단하지만 더 나은 해결책이있을 수 있습니다.

두 어레이 간의 거리 값을 찾기위한 최적화 된 접근 방식 Leetcode 솔루션

위의 접근 방식에서는 두 개의 중첩 루프를 사용했습니다. 그러나 결국 우리는 첫 번째 배열의 현재 요소가 d보다 작은 차이를 가진 두 번째 배열의 단일 요소를 가지고 있는지 확인하기 만하면됩니다. 따라서 첫 번째 배열에서 선택한 요소에 가장 가까운 두 요소를 선택하면. 이 두 개의 가장 가까운 요소가 d보다 작은 최소 절대 차이를 가지지 않으면 다른 요소가 더 나은 결과를 생성 할 수 없다고 확신 할 수 있습니다.

따라서 문제는 이제 두 번째 배열에서 첫 번째 배열의 선택한 요소에 가장 가까운 두 요소를 찾는 것으로 요약됩니다. 이 두 개의 가장 가까운 요소를 찾기 위해 두 번째 배열을 정렬하고 이진 검색을 사용합니다. 이진 검색을 사용하여 선택한 요소보다 크거나 같은 요소를 찾습니다. 현재 요소보다 작은 요소도 차이를 평가하는 데 사용됩니다.

이러한 차이가 d보다 작 으면 요소에 플래그를 지정하고 답에 포함하지 않습니다. 나머지 요소는 답에 포함되며 함수의 끝에 반환됩니다.

두 배열 간의 거리 값을 찾기 위해 최적화 된 코드 Leetcode 솔루션

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
    int ans = 0;
    sort(arr2.begin(), arr2.end());
    for(int i=0;i<arr1.size();i++){
        int it = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
        bool isIt = false;
        if(it<arr2.size() && abs(arr2[it] - arr1[i]) <= d)isIt = true;
        if(it != 0 && abs(arr2[it-1] - arr1[i]) <= d)isIt = true;
        if(!isIt)
            ans++;
    }
    return ans;
}

int main(){
    vector<int> arr1 = {4,5,8};
    vector<int> arr2 = {10,9,1,8};
    int d = 2;
    cout<<findTheDistanceValue(arr1, arr2, d);
}
2

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  private static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int i= 0;i<arr1.length;i++) {
            int it = Arrays.binarySearch(arr2, 0, arr2.length, arr1[i]);
            if (it < 0) it = -(it+1);
            boolean isIt = false;
            if(it<arr2.length && Math.abs(arr2[it] - arr1[i]) <= d)isIt = true;
            if(it != 0 && Math.abs(arr2[it-1] - arr1[i]) <= d)isIt = true;
            if(!isIt)
                ans++;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] arr1 = {4,5,8};
      int[] arr2 = {10,9,1,8};
      int d = 2;
      System.out.print(findTheDistanceValue(arr1, arr2, d));
  }
}
2

복잡성 분석

시간 복잡성

O (최대 (M, N) logN), 두 번째 배열을 정렬하고 첫 번째 배열의 각 요소에 대해 이진 검색을 수행하기 때문입니다. 여기서 M, N은 각각 첫 번째 및 두 번째 배열의 요소 수입니다.

공간 복잡성

의 위에), 두 번째 배열을 정렬하는 데 필요한 공간입니다.