题解 | #远亲不如近邻#

思路：

题目的主要信息：

a数组是每个邻居在坐标上的位置（一维坐标），x数组牛牛搬家之后在坐标上的位置
要求每次搬家后最近邻居的最近距离

方法一：暴力法
具体做法：
对于每一种搬家方案，遍历每个邻居的位置，直接算出距离维护最小值。

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        vector<int> res;
        for(int i = 0; i < m; i++){
            int mindis = INT_MAX;
            for(int j = 0; j < n; j++) //遍历每个邻居找到最小值
                mindis = min(mindis, abs(a[j] - x[i]));
            res.push_back(mindis);
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nm)$ ，两层循环，遍历长度分别是 $m$ 和 $n$
空间复杂度： $O(1)$ ，res是返回函数必要空间，不属于额外空间

方法二：排序+二分法
具体做法：
因为我们要找到 $x[i]$ 离谁更近，更近的无非就是刚好比它大或者比小，因此我们可以对数组a进行排序，然后利用二分查找找到刚好比 $x[i]$ 大的位置，比较前后谁的距离更小。
需注意边界的处理。
图片说明

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        vector<int> res;
        sort(a.begin(), a.end());
        for(int i = 0; i < m; i++){
            auto iter = lower_bound(a.begin(), a.end(), x[i]); //二分查找
            if(iter == a.begin()) //找到最前一个元素
                res.push_back(abs(a[0] - x[i]));
            else if(iter == a.end()) //没找到
                res.push_back(abs(a[n - 1] - x[i]));
            else
                res.push_back(min(abs(x[i] - *iter), abs(x[i] - *(iter - 1)))); //比较前后谁更近
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n)$ ，sort函数快排是 $O(nlog_2n)$ ，遍历为 $O(n)$ ，lower_bound函数属于二分查找 $O(log_2n)$
空间复杂度： $O(1)$ ，无额外空间使用