658 Find K Closest Elements
1. Question
Given a sorted array, two integersk
andx
, find thek
closest elements tox
in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 10^4
Absolute value of elements in the array and x will not exceed 10^4
2. Implementation
(1) Binary Search + Two Pointers
思路: 这道题非常多corner cases要注意考虑
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> res = new ArrayList<>();
if (arr == null || arr.length == 0) {
return res;
}
int n = arr.length;
if (x <= arr[0]) {
return getSubArray(res, arr, 0, k - 1);
}
else if (x >= arr[n - 1]) {
return getSubArray(res, arr, n - k, n - 1);
}
else {
int index = binarySearch(arr, x);
int low = Math.max(0, index - k);
int high = Math.min(n - 1, index + k);
while (high - low + 1 > k) {
if (low < 0 || ((x - arr[low]) <= (arr[high] - x))) {
--high;
}
else if (high >= n || ((arr[high] - x) < (x - arr[low]))) {
++low;
}
else {
break;
}
}
return getSubArray(res, arr, low, high);
}
}
public List<Integer> getSubArray(List<Integer> res, int[] arr, int start, int end) {
for (int i = start; i <= end; i++) {
res.add(arr[i]);
}
return res;
}
public int binarySearch(int[] nums, int target) {
int start = 0, end = nums.length - 1, mid = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] < target) {
start = mid + 1;
}
else {
end = mid;
}
}
return nums[start] >= target ? start : end;
}
}
3. Time & Space Complexity
Binary Search + Two Pointers: 时间复杂度O(logn + k), 空间复杂度O(k)
Last updated
Was this helpful?