思路
题目分析
- 题目要求我们在一维城镇中选取一个轴上的位置居住,给出若干可选的居住点方案,计算每一个方案对应的距离居住居民的最小值。
- 其中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; } };
复杂度分析
- 时间复杂度:,排序居民居住位置开销,对每种方案进行二分确定区间开销
- 空间复杂度:,没有借助额外辅助空间