文章目录

1、题目描述2、解题思路3、解题代码

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); } } }