题目
给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。
示例 1:
输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]
示例 2:
输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]
说明:
- k 的值为正数，且总是小于给定排序数组的长度。
- 数组不为空，且长度不超过 104
- 数组里的每个元素与 x 的绝对值不超过 104
思路
首先这是一个有序的数组，那就可以先二分法查找x，然后返回对于的索引，这个分几种情况
1）找到等于x的值，直接返回索引
2）找不到具体等于x的值，就只能找到离x最近且最小的索引值
根据上面返回的索引值，作为第二步的初始索引。分别判断前后的是不是到上下边界了，
1）没到边界，分别找前后离x最近的边界，左或右移一位
2）到边界，只能反向移动，左移或右移动一位
结束条件是k，每次移动边界，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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| class Solution {
public int binarySearch(int[] arr,int x){
int left = 0;
int right = arr.length -1;
while(left <= right){
int index = (right -left)/2+left;
int value = arr[index];
if(value == x){
return index;
}else if(value > x){
right = index - 1;
}else if(value < x){
if(index + 1 < (arr.length -1)){
int next = arr[index+1];
if(next < x){
left = index + 1;
continue;
}
int comp = (next - x) - (x - value);
if(comp >= 0){
return index;
}else{
return index+1;
}
}else{
return index;
}
}
}
return -1;
}
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int flag = binarySearch(arr,x);
if(flag == -1){
List<Integer> list = new ArrayList<Integer>();
for(int i = 0 ; i<k;i++){
list.add(arr[i]);
}
return list;
}
int nums = k-1;
int left = flag;
int right = flag;
int size = arr.length;
while(nums != 0){
int innerLeft = left;
int innerRight = right;
if(right + 1 > size -1){
left = innerLeft -1;
nums--;
continue;
}else if(left -1 < 0){
right = innerRight + 1;
nums--;
continue;
}else{
if( right + 1 <= size - 1 ){
innerRight = innerRight + 1;
}
if(left -1 >= 0){
innerLeft = innerLeft -1;
}
}
int leftValue = arr[innerLeft];
int rightValue = arr[innerRight];
int leftDiv = x - leftValue;
int rightDiv = rightValue - x;
if(leftDiv <= rightDiv){
left = innerLeft;
}else{
right = innerRight;
}
nums--;
}
List<Integer> list2 = new ArrayList<Integer>();
for(int i = left ; i<= right;i++){
list2.add(arr[i]);
}
return list2;
}
}
|
比较容易出错的有几点
1.二分查找不光要找出等于的值，也要查找离的最近最小的值
2.第二次进行查询的时候，可能会有相等数字重复多次的情况，也要考虑
3.第二次查找，比较大小左右边界移动的判断条件很复杂，很容易出错。
