一、环境说明

1. 本文是 LeetCode 1385题 : 两个数组间的距离值,使用c语言实现
2. 测试环境:Visual Studio 2019

二、代码展示

int cmp(const void* a_, const void* b_) {
    return *(int*)a_ - *(int*)b_;
}
int findTheDistanceValue(int* arr1, int arr1Size, int* arr2, int arr2Size, int d) {
    qsort(arr2, arr2Size, sizeof(int), cmp);//快排arr2
    int dis = 0;//距离
    for (int i = 0; i < arr1Size; i++) {
        int left = 0, right = arr2Size - 1, mid = 0;
        int curNum1 = arr1[i];//curNum1保存当前参与比较的arr1中的数
        while (left <= right) {//二分查找
            mid = left + ((right - left) >> 1);
            if (curNum1 - arr2[mid] > d) {//说明curNum1>arr2[mid]，可以找更大的arr2[mid]，来逼近d
                left = mid + 1;//往右边移动
            }
            else if (curNum1 - arr2[mid] < -d) {//为了逼近-d,需要找更小的arr2[mid]
                right = mid - 1;//往左移动
            }
            else {//|curNum1-arr2[mid]|<=d
                break;
            }
        }
        if (left>right) {//查找完毕，curNum1符合条件
            dis++;
        }
    }
    return dis;
}

三、代码分析

1. 初刷本题，一定要知道，形参和题目的对应关系。因为题目描述里，没有解释这些参数，所以直接看答案效率更高。
2. 整体思路：将arr2中的元素排序，从小到大。遍历arr1，如果|arr1[i]-arr2[j]|>d，为了逼近d，甚至小于等于d，改变left或者right，找到最可能逼近d的位置，这个过程就是二分查找。
3. cmp()是一个排序规则函数，服务于qsort()库函数。
4. qsort()是快速排序

四、AC

五、复杂度分析

1. 时间复杂度:O(nlog₂n+mlog₂n)，n是arr2的长度，m是arr1的长度。nlog₂n是快排时间复杂度，mlog₂n是遍历arr1同时二分查找arr2的时间复杂度。
2. 空间复杂度:O（1），除若干变量使用的常量空间外，没有使用线性空间

相关链接:
(c语言)LeetCode1337. The K Weakest Rows in a Matrix
这道题也使用了快排+二分查找的思想，有能力的读者可以继续学习这些算法。