Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or|a - x| == |b - x| and a < b
Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]
Example 2:
Input: arr = [1,2,3,4,5], k = 4, x = -1 Output: [1,2,3,4]
Constraints:
1 <= k <= arr.length1 <= arr.length <= 104arr is sorted in ascending order.-104 <= arr[i], x <= 104// class Solution {
// public:
// struct comparator{
// int x;
// comparator(int x){
// this->x=x;
// }
// bool operator ()(int a, int b){
// return abs(a-x)<abs(b-x);
// }
// };
// vector<int> findClosestElements(vector<int>& arr, int k, int x) {
// if(arr.size()==1) return arr;
// stable_sort(arr.begin(), arr.end(), comparator(x));
// arr=vector<int>(arr.begin(),arr.begin()+k);
// // arr.erase(arr.begin()+k, arr.end());
// sort(arr.begin(), arr.end());
// return arr;
// }
// };
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
if(arr.size()==1 || arr.size()==k) return arr;
int lt=0, rt=arr.size()-1;
while(rt-lt>=k)
x-arr[lt]>arr[rt]-x?lt++:rt--;
return vector<int>(arr.begin()+lt, arr.begin()+rt+1);
}
};