README.md

658. 找到 K 个最接近的元素

English Version

题目描述

给定一个排序好的数组 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 <= 104
• 数组里的每个元素与 x 的绝对值不超过 104

解法

Python3

Java

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        if (arr.length < k) {
            for (int item : arr) {
                res.add(item);
            }
            return res;
        }
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (arr[mid] > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        int left1 = 0;
        int right1 = arr.length - 1;
        if (left >= k) {
            left1 = left - k;
        }
        if (arr.length - 1 - left >= k) {
            right1 = left + k;
        }
        while (right1 - left1 >= k) {
            if (Math.abs(arr[left1] - x) > Math.abs(arr[right1] -x)) {
                left1++;
            } else {
                right1--;
            }
        }
        while (left1 <= right1) {
            res.add(arr[left1]);
            left1++;
        }
        return res;
    }
}

...