数组距离

算法

Posted by CH on May 20, 2020

题目

给你两个整数数组 arr1 , arr2 和一个整数 d ,请你返回两个数组之间的 距离值 。

「距离值」 定义为符合此距离要求的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足 arr1[i]-arr2[j] <= d 。

示例

输入arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出2
解释
对于 arr1[0]=4 我们有
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
所以 arr1[0]=4 符合距离要求

对于 arr1[1]=5 我们有
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
所以 arr1[1]=5 也符合距离要求

对于 arr1[2]=8 我们有
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
存在距离小于等于 2 的情况不符合距离要求 

故而只有 arr1[0]=4  arr1[1]=5 两个符合距离要求距离值为 2

题干

arr1[i]-arr2[j] <= d 为不符合要求
arr1[i]-arr2[j] > d 符合要求

对于arr[i] 如果有一项 arr2[j] 不符合要求距离值+1

思路

暴力循环

根据其定制的规则 循环数组arr1 在其中循环arr2

并且判断如果有不符合要求的 直接break循环 距离值+1

循环优化

对于嵌套循环的场景 我们考虑下是否可以将循环平铺 从循环中找到 优化点

从题干入手 即对于arr[i]来说 如何使得arr1[i]-arr2[j]足够小 让其不符合要求 如果这种极端情况都符合 那么肯定符合要求

也就是说 我们找到两个数使得传入的arr[i]与其足够小即可 第一个比这个大的数和第一个比这小的数

有没有熟悉的味道 这正好符合排序的顺序规则 我们只要把arr2数组排序 找到arr[i]在这个数组的位置 那么这个位置的前一个和后一个位置的数

我们不就可以知道 不就可以不通过循环判断是否符合条件了吗

解答

暴力循环

public class Solution {
      public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int distance = 0; int flag = 0 ;
        for(int i=0;i<arr1.length;i++){
            for(int j=0;j<arr2.length;j++){
                int distanceD = Math.abs(arr2[j]-arr1[i]); //差值
                if(distanceD<=d){ //不符合要求 直接break循环
                    flag=1;
                    break;
                }
            }//一次i循环 如果有不符合要求的distance+1
            if (flag == 0 ) {
                distance ++ ;
            } else {
                flag = 0 ;
            }
        }
        return distance;
    }
}

循环优化

public class Solution {
    public static int findTheDistanceValue2(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int distance = 0; int flag = 0 ; 
        for(int i=0;i<arr1.length;i++){
            int p = binarySearch(arr2, arr1[i]); //找到这个数在数组的位置 比他大的位置
            boolean ok = true;
            if(p<arr2.length){ //如果是大的不符合 
                ok &= Math.abs(arr2[p]-arr1[i])>=d; 
            }
            if (p - 1 >= 0 && p - 1 <= arr2.length) { //如果小的不符合
                ok &= arr1[i] - arr2[p - 1] > d;
            }
            distance += ok ? 1 : 0; //同时不符合即distance+1
        }
        return distance;
    }
    
    public static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        if (arr[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

时空复杂度分析

如果采用暴力循环解法 时间复杂度为O(m*n) 空间复杂度为O(1) 没有用到辅助空间

如果采用只加个位解法 时间复杂度为O(nlogm)+O(mlogm) 前面部分是二分的时间 后面是排序的时间 空间复杂度为O(1)

解题技巧 总结形成套路

结语

此题涉及到 循环和条件判断 还有我们是否有办法根据条件去优化循环 去掉没有意义的循环

有的时候循环确实能解决问题 但是其所产生的代价也是巨大的 掌握优化循环的方法 能使得我们的算法更加的好