题解 | #远亲不如近邻#

思路

题目分析

1. 题目要求我们在一维城镇中选取一个轴上的位置居住，给出若干可选的居住点方案，计算每一个方案对应的距离居住居民的最小值。
2. 其中n表示居民个数，m表示可选的方案数量，a表示具体的居民居住方案，x表示牛牛可选方案

• 一种方法就是我们枚举所有的居民居住的位置，分别与所有的可选方案进行一一距离计算，对每一种方案取一个最小值，就是最终结果
• 另一种方法利用二分法，对居民居住位置首先排序，然后将我们的方案用二分的方法去找一个最优的区间，然后分别计算和左邻居右邻居的距离取最小值，就是当前方案的最短距离。

方法一：暴力枚举

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;
        for(int loc : x) {                        // 遍历牛牛的可选位置
            int mn = INT_MAX;
            for(int home : a) {                   // 遍历居民的所有位置
                mn = min(mn, abs(home - loc));    // 对可选位置和每个居民的位置进行距离测算并保留最小值
            }
            res.push_back(mn);                    // 将结果收在res中最终返回
        }
        return 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
        sort(a.begin(),a.end());                    // 排序数组a，使居民按照下标顺序排序
        vector<int> res;                            // 最终结果返回数组
        for(int loc : x) {                          // 遍历牛牛的可选方案
            int l = 0;
            int r = a.size()-1;
            int dis = INT_MAX;
            while(l <= r) {                         // 进行二分循环判断
                int mid = (l+r)/2;
                if(a[mid] == loc) {                 // 如果左右中点正好是牛牛可选点
                    dis = 0;                        // 则标记距离=0
                    break;
                }
                if(a[mid] > loc) {                  // 如果中间值大，则调整到左子区间进行二分查找
                    r = mid-1;
                }else {                             // 如果中间值小，则调整到右子区间进行二分查找
                    l = mid+1;
                }
            }

            // 定位好最终牛牛可选方案所被夹在的两个居民中间的时候，分别计算到两个居民居住的距离，取最小的到dis中
            if(l < a.size()) dis = min(dis, abs(a[l] - loc));
            if(r >= 0) dis = min(dis, abs(a[r] - loc));

            res.push_back(dis);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：，排序居民居住位置开销，对每种方案进行二分确定区间开销
• 空间复杂度：，没有借助额外辅助空间