LeetCode_排序_二分搜索_双指针_中等_658.找到 K 个最接近的元素

1.题目

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

• |a - x| < |b - x| 或者
• |a - x| == |b - x| 且 a < b

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

提示：
1 <= k <= arr.length
1 <= arr.length <= 10⁴
arr 按升序排列
-104 <= arr[i], x <= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-k-closest-elements

2.思路

（1）排序
首先将数组 arr 按照题目中更接近的定义进行排序，即越接近 x 的数越排在前面。排序之后的前 k 个数即为 k 个最接近 x 的元素，此时将这 k 个元素进行升序排序后再直接返回即可。

（2）二分搜索 & 双指针
思路参考本题官方题解。

3.代码实现（Java）

//思路1————排序
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> arrList = new ArrayList<>();
        for (int num : arr) {
            arrList.add(num);
        }
        arrList.sort((a, b) -> {
            //按照题目中更接近 x 的定于对 arrList 中的数进行排序
            if (Math.abs(a - x) != (Math.abs(b - x))) {
                return Math.abs(a - x) - Math.abs(b - x);
            } else {
                return a - b;
            }
        });
        // arrList 中的前 k 个数即为 k 个最接近 x 的元素
        List<Integer> res = arrList.subList(0, k);
        // 对 res 进行升序排序
        Collections.sort(res);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//思路2————二分搜索 & 双指针
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int right = leftBoundSearch(arr, x);
        int left = right - 1;
        while (k-- > 0) {
            if (left < 0) {
                right++;
            } else if (right >= arr.length) {
                left--;
            } else if (x - arr[left] <= arr[right] - x) {
                left--;
            } else {
                right++;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = left + 1; i < right; i++) {
            res.add(arr[i]);
        }
        return res;
    }
    
    //查找 target 在数组 arr 中的最左边界
    public int leftBoundSearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
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