LeetCode 658. 找到 K 个最接近的元素
原题链接
中等
作者:
@Dorian
,
2021-01-21 02:02:31
,
所有人可见
,
阅读 347
先二分找点,再双指针$O(logn + k)$
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
if (arr[0] >= x) return vector<int>(arr.begin(), arr.begin() + k);
else if (arr.back() <= x) return vector<int>(arr.end() - k, arr.end());
const int n = arr.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] < x) l = mid + 1;
else r = mid;
}
--l;
vector<int> ans(k);
int c = 0;
while (c < k) {
int left = INT_MAX, right = INT_MAX;
if (l >= 0) left = abs(arr[l] - x);
if (r < n) right = abs(arr[r] - x);
if (left <= right) --l, ++c;
else ++r, ++c;
}
for (int i = l + 1, j = 0; i < r; i++, j++) ans[j] = arr[i];
return ans;
}
};
直接二分$O((n-k)log(n-k))$
class Solution {
public:
vector<int> findClosestElements(vector<int>& a, int k, int x) {
const int n = a.size();
int l = 0, r = n - k;
while(l < r){
int mid = l + r >> 1;
if(x - a[mid] > a[mid + k] - x)
l = mid + 1;
else r = mid;
}
return vector<int>(a.begin() + l, a.begin() + l + k);
}
};