📃 题目描述

题目链接：658. 找到 K 个最接近的元素 (opens new window)

🔔 解题思路

美团一面的原题，一开始想的暴力排序，后来面试官引导了很久才想出来二分查找 + 双指针

二分查找到 x 的位置（注意这里 x 可能不存在于 arr 中），然后左右指针找 k 个最接近 x 的数

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();

        int index = getX(arr, x);

        // 这里【不】应该初始化为 left = index, right = index + 1
        // ex: [0,0,1,2,3,3,4,7,7,8] k = 3, x = 5
        int left = index - 1, index;
        while (k != 0 && (left >= 0 || right < arr.length)) {
            int l = (left >= 0) ? Math.abs(arr[left] - x) : Integer.MAX_VALUE;
            int r = (right < arr.length) ? Math.abs(arr[right] - x) : Integer.MAX_VALUE;

            if (l <= r) {
                left --;
            }
            else {
                right ++;
            }

            k --;
        }

        for (int i = left + 1; i <= right - 1; i ++) {
            list.add(arr[i]);
        }

        return list;
    }

    // 找到 x 的下标，如果 x 不存在，返回第一个比 x 大的元素的下标
    private int getX(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] == x) {
                return mid;
            }
            else if (arr[mid] > x) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return left;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：