0658. Find K Closest Elements
https://leetcode.com/problems/find-k-closest-elements
Description
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.length
1 <= arr.length <= 104
arr
is sorted in ascending order.-104 <= arr[i], x <= 104
ac
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
// edge cases
// find x index
int idx = findIndex(arr, x);
// get k element
List<Integer> res = new ArrayList<Integer>();
int l = idx - 1, r = idx;
if (arr[r] == x) {
res.add(arr[r]);
r++;
}
while (res.size() < k) {
// take left
if (r >= arr.length || l >= 0 && x - arr[l] <= arr[r] - x) {
res.add(0, arr[l--]);
} else { // take right
res.add(arr[r++]);
}
}
return res;
}
private int findIndex(int[] arr, int x) {
int res = -1, l = 0, r = arr.length - 1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) return mid;
if (x < arr[mid]) r = mid;
else l = mid;
}
// final check
if (x <= arr[l]) return l;
else if (x <= arr[r]) return r;
else return r+1;
}
}
/*
find index, compare left and right side, get smaller one
*/
Last updated
Was this helpful?