658 Find K Closest Elements

1. Question

Given a sorted array, two integerskandx, find thekclosest elements toxin the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
1
Input: [1,2,3,4,5], k=4, x=3
2
3
Output: [1,2,3,4]
Copied!
Example 2:
1
Input: [1,2,3,4,5], k=4, x=-1
2
3
Output: [1,2,3,4]
Copied!
Note:
  1. 1.
    The value k is positive and will always be smaller than the length of the sorted array.
  2. 2.
    Length of the given array is positive and will not exceed 10^4
  3. 3.
    Absolute value of elements in the array and x will not exceed 10^4

2. Implementation

(1) Binary Search + Two Pointers
思路: 这道题非常多corner cases要注意考虑
1
class Solution {
2
public List<Integer> findClosestElements(int[] arr, int k, int x) {
3
List<Integer> res = new ArrayList<>();
4
5
if (arr == null || arr.length == 0) {
6
return res;
7
}
8
9
int n = arr.length;
10
11
if (x <= arr[0]) {
12
return getSubArray(res, arr, 0, k - 1);
13
}
14
else if (x >= arr[n - 1]) {
15
return getSubArray(res, arr, n - k, n - 1);
16
}
17
else {
18
int index = binarySearch(arr, x);
19
int low = Math.max(0, index - k);
20
int high = Math.min(n - 1, index + k);
21
22
while (high - low + 1 > k) {
23
if (low < 0 || ((x - arr[low]) <= (arr[high] - x))) {
24
--high;
25
}
26
else if (high >= n || ((arr[high] - x) < (x - arr[low]))) {
27
++low;
28
}
29
else {
30
break;
31
}
32
}
33
return getSubArray(res, arr, low, high);
34
}
35
}
36
37
public List<Integer> getSubArray(List<Integer> res, int[] arr, int start, int end) {
38
for (int i = start; i <= end; i++) {
39
res.add(arr[i]);
40
}
41
return res;
42
}
43
44
public int binarySearch(int[] nums, int target) {
45
int start = 0, end = nums.length - 1, mid = 0;
46
47
while (start + 1 < end) {
48
mid = start + (end - start) / 2;
49
50
if (nums[mid] < target) {
51
start = mid + 1;
52
}
53
else {
54
end = mid;
55
}
56
}
57
return nums[start] >= target ? start : end;
58
}
59
}
Copied!

3. Time & Space Complexity

Binary Search + Two Pointers: 时间复杂度O(logn + k), 空间复杂度O(k)