1、题目描述
2、解题思路
题目给定的函数返回的是 List 类型,List 有一个方法和字符串类似,为 subList(a,b),返回 list 区间 [a,b) 的子序列。
先把给定的 arr 数组转成 List 类型 ret。
1、如果 x 比 ret 的第一个元素还小,则返回 ret 的前面 k 个元素;
2、如果 x 比 ret 的最后一个元素还大,则返回 ret 最后 k 个元素;
3、如果 x 不满足上面两个,则:
3.1 调用 Collections 的 binarySearch 方法,返回一个 index,如果 x 存在于 ret 中,则返回 x 在 ret 中的下标;如果 x 不存在于 ret 中,则返回的 index 表示“如果 x 要插入到 ret 中,则应该插入在 -index-1 的位置中”;
3.2 确定一个区间 [index-k-1, index+k-1] 作为初始区间,不断比较 x 到左边界和右边界的距离大小,谁大则谁往中间缩小边界;
3.3 当边界内的元素为 k 个时,则该 k 个元素就是答案。
3、解题代码
import java.util.*;
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> ret = Arrays.stream(arr).boxed().collect(Collectors.toList());
int n = ret.size();
if (x <= ret.get(0)) {
return ret.subList(0, k);
} else if (ret.get(n - 1) <= x) {
return ret.subList(n - k, n);
} else {
int index = Collections.binarySearch(ret, x);
if (index < 0){
index = -index - 1;
}
int low = Math.max(0, index - k - 1);
int high = Math.min(ret.size() - 1, index + k - 1);
while (high - low > k - 1) {
if ((x - ret.get(low)) <= (ret.get(high) - x)){
high--;
}else{
low++;
}
}
return ret.subList(low, high + 1);
}
}
}