找到 K 个最接近的元素

题目链接

找到 K 个最接近的元素

题目描述

注意

• 1 <= k <= arr.length
• arr按升序排列

解答思路

• 首先找到最接近元素x的索引idx，再以idx为准向左取k个元素（如果越界则从位置0开始取），确定左右指针，再比较左指针处的元素与右指针往右一位的元素哪个更接近x，以此类推左右指针指向的就是最接近x的k个元素

代码

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        int idx = 0;
        int min = Integer.MAX_VALUE;
        // 找到最接近x的元素索引
        for(int i = 0; i < n; i++) {
            int sub = Math.abs(arr[i] - x);
            if(sub < min) {
                idx = i;
                min = sub;
            }
        }
        // 从最接近x的元素开始取左侧的k个数（如果可以）
        int left = idx - k + 1;
        int right = idx;
        // 防止左指针越界
        if(left < 0) {
            left = 0;
            right = k - 1;
        }
        // 找到最接近x的k个数
        for(int i = 0; i < k - 1; i++) {
            // 如果此时右指针右侧的元素比左指针指向的元素更接近x，左右指针右移一位
            if(right + 1 < n && Math.abs(arr[left] - x) > Math.abs(arr[right + 1] - x)) {
                left++;
                right++;
            } else break;
        }
        List<Integer> res = new ArrayList<>();
        for(int i = left; i <= right; i++) {
            res.add(arr[i]);
        }
        return res;
    }
}

关键点

• 找到一个基准查找到更有可能接近x的子数组
• 注意越界问题