题解 | #远亲不如近邻#

题解一:暴力
主要思路：
①遍历方案数组，依次选取方案i
②遍历居民位置，计算距离
③对一个方案的所有距离求出最小距离，存入res数组

图示:

复杂度分析:
时间复杂度分析:，通过遍历每一个方案数，在与每一个居民计算距离，所以时间复杂度为;
空间复杂度分析:，除返回结果数组外，没有申请其他额外空间

实现如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        // write code here
        vector<int> res(m);//提前申请好数组，减少vector中间扩容所需要的时间。
        for(int i=0;i<x.size();i++){
            int min_L=INT_MAX;//临时变量，存储当前方案的最小距离，初始值为INT_MAX
            for(int j=0;j<a.size();++j){
                int temp=abs(a[j]-x[i]);//计算出当前方案数i与居民j的距离
                min_L=min(min_L,temp);//求出最小距离
            }
            res[i]=min_L;//将结果加入res数组
        }
        return res;//返回结果
    }
};

题解二：二分
主要思路：
①将居民位置进行排序（刚开始没有AC的原因）
②遍历方案数组，依次选取方案i
③二分查找居民位置，计算出最近距离
④将二分查找的最小距离，存入res数组
图示:

复杂度分析:
时间复杂度分析:，通过遍历每一个方案数为，在居民中二分找最近的距离，排序时间;
空间复杂度分析:，除返回结果数组外，没有申请其他额外空间

实现如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        sort(a.begin(),a.end());
        vector<int> res(m);//提前申请好数组，减少vector中间扩容所需要的时间。
        for (int i = 0; i < m; i++) {//遍历每一种方案
            int l = 0, r = n - 1;
            int mid = l + (r - l) / 2;//中心位置，不用（l+r）/2的原因可能会爆int数据
            int temp_ans = abs(a[mid] - x[i]);//求出搬家方案x[i]与中心位置的距离
            while (l < r) {//二分查找的判断条件
                if(x[i] == a[mid]){//刚好与居民重叠，最优选择，退出二分查找
                    temp_ans = 0;
                    break;
                }
                if (x[i] > a[mid])l = mid + 1;//搬家位置处于居民点的右侧，左侧居民肯定离搬家点越远
                else if (x[i] < a[mid])r = mid - 1;//搬家位置处于居民点的左侧，右侧居民肯定离搬家点越远
                mid = l + (r - l) / 2;//继续求中心点
                temp_ans = min(temp_ans, abs(a[mid]-x[i]));//获取最小的距离
            }
            res[i] = temp_ans;//存入结果数组
        }
        return res;
}
};