给定排序好的数组 arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的
1. 通用调库解法
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;});
//注意vector的指针实际上是左闭右开
sort(arr.begin(), arr.begin() + k);
return vector<int>(arr.begin(), arr.begin() + k);
}
};
2. 二分法+双指针
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();//第一个大于x的值下标
int left = right - 1;//小于等于x的值下标
while (k--) {//循环找k次,此时left、right皆为开区间
if (left < 0) right++;//左指针溢出
else if (right >= arr.size()) left--;//右指针溢出
else if (x - arr[left] <= arr[right] - x) left--;//左侧值相等或更小移动左指针
else right++;//否则移动右指针
}
//实际上输出的是[left+1,right-1]区间
return vector<int>(arr.begin() + left + 1, arr.begin() + right);
}
};
标签:begin,right,int,元素,arr,vector,接近,LeetCode,left
From: https://www.cnblogs.com/929code/p/16622867.html