Algorithm
Problem Name: 658. Find K Closest Elements
Problem Link: https://leetcode.com/problems/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|anda < 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 <= 104arris sorted in ascending order.-104 <= arr[i], x <= 104
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int>res;
int pos = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
int i = pos - 1, j = pos;
while(k--)
(i >= 0 && (j == arr.size() || abs(arr[i] - x) < = abs(arr[j] - x))) ? i-- : j++;
res.assign(arr.begin() + i + 1, arr.begin() + j);
return res;
}
};
Input
arr = [1,2,3,4,5], k = 4, x = 3
Output
[1,2,3,4]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List findClosestElements(int[] arr, int k, int x) {
List result = new ArrayList<>();
if (arr.length == k) {
for (int num : arr) {
result.add(num);
}
return result;
}
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
left--;
right = left + 1;
while (right - left - 1 < k) {
if (left == -1) {
right++;
continue;
}
if (right == arr.length || Math.abs(arr[left] - x) < = Math.abs(arr[right] - x)) {
left--;
} else {
right++;
}
}
for (int i = left + 1; i < right; i++) {
result.add(arr[i]);
}
return result;
}
}
Input
arr = [1,2,3,4,5], k = 4, x = 3
Output
[1,2,3,4]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findClosestElements = function(arr, k, x) {
let lo = 0, hi = arr.length - k - 1;
while (lo < = hi) {
let mid = Math.floor(lo + (hi - lo) / 2);
if (Math.abs(x - arr[mid]) > Math.abs(x - arr[mid+k])) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return arr.slice(lo, lo+k);
};
Input
arr = [1,2,3,4,5], k = 4, x = -1
Output
[1,2,3,4]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findClosestElements(self, arr, k, x):
ind, n = bisect.bisect_left(arr, x), len(arr)
if ind > 0 and x - arr[ind - 1] < arr[ind] - x: ind -= 1
l, r = ind, ind + 1
for _ in range(k - 1):
if r >= n or (l > 0 and x - arr[l - 1] <= arr[r] - x): l -= 1
else: r += 1
return arr[l:r]
Input
arr = [1,2,3,4,5], k = 4, x = -1
Output
[1,2,3,4]