658. Find K Closest Elements

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.length
  • 1 <= arr.length <= 104
  • arr is sorted in ascending order.
  • -104 <= arr[i], x <= 104
class Solution {
public:
vector<int> findClosestElements(vector<int>& v, int k, int x) {
int st = 0, end = v.size() - 1;
while (end-st>=k) {
if(x-v[st]<=v[end]-x)end--;
else st++;
}
return vector<int>(v.begin() + st, v.begin() + end + 1);
}
};
Made with ❤ by Raunit Verma Rate Us 5⭐ Here
class Solution {
public:
vector<int> findClosestElements(vector<int>& v, int k, int x) {
int st = 0, end = v.size() - k;
while (st < end) {
int mid = (st + end) / 2;
if (x - v[mid] > v[mid + k] - x)
st = mid + 1;
else
end = mid;
}
return vector<int>(v.begin() + st, v.begin() + st + k);
}
};
view raw 658. Find K Closest Elements1.cpp hosted with ❤ by GitHub