查找兩個陣列Leetcode解決方案之間的距離值


難度級別 容易獎學金
經常問 尤伯杯
排列

問題發現兩個之間的距離值 數組 Leetcode解決方案為我們提供了兩個數組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

Java代碼

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(max(M,N)logN), 因為我們對第二個數組進行排序並對第一個數組中的每個元素執行二進制搜索。 在此,M,N分別是第一數組和第二數組中的元素數。

空間複雜度

上), 排序第二個數組所需的空間。