查找两个阵列Leetcode解决方案之间的距离值  


难度级别 易得奖学金
经常问 尤伯杯
算法 排列 编码 访谈 面试准备 力码 力码解决方案

问题发现两个之间的距离值 数组 Leetcode解决方案为我们提供了两个数组arr1和arr2。 除了两个数组,我们还提供了一个整数n。 然后问题问我们找出给定两个数组之间的相对距离。 相对距离定义为第一数组中元素的数量,该元素在第二数组中不具有任何最小绝对差小于或等于给定整数d的元素。 因此,像往常一样,在深入研究解决方案之前,我们首先应该看一些示例。查找两个阵列Leetcode解决方案之间的距离值Pin

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,那么我们可以肯定地说没有其他元素可以产生更好的结果。

因此,问题现在归结为找到最接近第一个数组的两个元素(从第二个数组开始)。 为了找到这两个最接近的元素,我们对第二个数组进行排序并使用二进制搜索。 使用二进制搜索,我们发现等于或大于拾取的元素的元素。 刚好小于当前元素的元素也用于评估差异。

参见
使字符串成为出色的Leetcode解决方案

如果这些差异小于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分别是第一数组和第二数组中的元素数。

空间复杂度

上), 排序第二个数组所需的空间。