题解 | #远亲不如近邻#

题目描述
牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。

俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。

方法一：暴力解法

求解思路
对于求解本题，我们对每个方案的位置，求出所有居民位置，即可得到本题目的答案。

图片说明

解题代码

class Solution {
public:
  vector<int> solve(int n, int m, vector<int> a, vector<int> x)
  {
    vector<int> myt(m); // 声明数组
    for(int i = 0; i < m; ++i)
    {
        myt[i] = 2e9;
        for(int j = 0; j < n; ++j) myt[i] = min(myt[i], abs(x[i]-a[j])); // 更新结果
    }
      return myt; // 返回结果
  }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：优化求解

求解思路
对于本问题，我们可以对所有居民的位置进行排序，然后对每个方案进行讨论，找到中间位置，和其相邻的两个数，并计算其距离。

图片说明

解题代码

class Solution {
public:
  vector<int> solve(int n, int m, vector<int> a, vector<int> x)
  {
    sort(a.begin(), a.end()); // 快排
    vector<int> t(m);
    for(int i = 0; i < m; ++i)
    {
        int myval = x[i];
        int myans = 2e9;
        if(myval < a[0])
            myans = a[0]-myval; // 记录返回值
        else
        {
            int l = 0, r = n-1;
            while(l <= r)
            {   //二分法的思想
                int mid = (r+l)>>1;
                if(a[mid] <= myval)
                {
                    myans = min(myans, myval-a[mid]); 
                    l = mid+1;
                }
                else
                    r = mid-1;
            }
        }
        if(myval > a[n-1])
            myans = min(myans, myval-a[n-1]);
        else
        {
            int l = 0, r = n-1;
            while(l <= r)
            {   //二分法的思想
                int mid = (r+l)>>1;
                if(a[mid] >= myval){myans = min(myans, a[mid]-myval); r = mid-1;}
                else l = mid+1;
            }
        }
        t[i] = myans;
    }
      return t; // 返回结果即可
}
};

复杂度分析
时间复杂度：使用二分法，因此时间复杂度为 $O(nlogn)$
空间复杂度：引入常数级变量空间，因此空间复杂度为 $O(1)$