05 August 2008
排序数组中找到距离给定数绝对值最近的的k个数 - 双指针/二分
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int size = arr.length;
int left = 0;
int right = size - 1;
int removeNums = size - k;
while (removeNums > 0) {
if (x - arr[left] <= arr[right] - x) {
right--;
} else {
left++;
}
removeNums--;
}
List<Integer> res = new ArrayList<>();
for (int i = left; i < left + k; i++) {
res.add(arr[i]);
}
return res;
}
}
二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int size = arr.length;
int left = 0;
int right = size - k;
while (left < right) {
// int mid = left + (right - left) / 2;
int mid = (left + right) >>> 1;
// 尝试从长度为 k + 1 的连续子区间删除一个元素
// 从而定位左区间端点的边界值
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1;
} else {
right = mid;
}
}
List<Integer> res = new ArrayList<>();
for (int i = left; i < left + k; i++) {
res.add(arr[i]);
}
return res;
}
}