题解 | #远亲不如近邻#

一.题目描述
NC533
牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。
图片说明
二.算法(暴力模拟)
理解题意可以知道要返回每一个到位置xi的最短距离，那么对于每一个方案遍历一遍居民位置数组就可以找到每一个方案对应最近的居民距离是多少。下面是完整代码：

class Solution {
public:
    vector<int> solve(int n, int m, vector<int> a, vector<int> x){
        vector<int> q(m);
        for(int i = 0; i < m; ++i){
            q[i] = 2e9;//开始是一个无穷大的值
            for(int j = 0; j < n; ++j) {
                q[i] = min(q[i], abs(x[i]-a[j]));
            }
        }
        return q;//返回答案
    }
};

时间复杂度： $O(n*m)$ 需要二重循环
空间复杂度： $O(m)$ 需要额外空间来存储结果
优缺点：思路简单且便于实现，但是时间复杂度高。
三.算法(二分)
对于算法二来说时间复杂度比较高，我们可以对其进一步优化，首先我们对居民位置数组进行排序，然后利用二分找到刚好比x[i]大的数或者刚好比x[i]小的数，最小距离就出在这两种情况，所以最优解很快就可以找到，在时间效率上得到了优化，下面是完整代码：

class Solution {
public:
  vector<int> solve(int n, int m, vector<int> a, vector<int> x){
    vector<int>q(m);//这块不熟悉c++的要注意了 直接复制前要为vecter申请空间
    sort(a.begin(), a.end()); // 首先进行排序,满足二分需要的单调性
    for(int i=0;i<m;i++){
        int num=x[i],ans=2e9;
        if(num<a[0]){
            ans=a[0]-num; // 记录返回值
        } else {
            int l=0,r=n-1;
            while(l<=r){   //二分查找
                int mid = (r+l)/2;
                if(a[mid]<=num){
                    ans=min(ans,num-a[mid]),l=mid+1;
                } else{
                    r=mid-1;
                }
            }
        }
        if(num>a[n-1]){
            ans = min(ans,num-a[n-1]);
        } else {
            int l=0, r=n-1;
            while(l<=r){   //二分查找
                int mid=(r+l)>>1;
                if(a[mid]>=num){
                    ans = min(ans, a[mid]-num);
                    r=mid-1;
                } else {
                    l=mid+1;
                }
            }
        }
        q[i]=ans;
    }
        return q; // 返回结果即可
    }
};

时间复杂度： $O(mlogn)$ 对于n次的遍历，每一次遍历进行二分的复杂度是 $logn$ ，所以时间复杂度是 $nlogn$
空间复杂度： $O(m)$ 需要额外空间来存储结果
优缺点：时间复杂度低，但是代码实现复杂