图解LeetCode——658. 找到 K 个最接近的元素（难度：中等）

标签：endIndex arr int 元素 midIndex startIndex 图解 LeetCode 658

一、题目

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

整数 a 比整数 b 更接近 x 需要满足：|a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b

二、示例

2.1> 示例 1：

【输入】arr = [1,2,3,4,5], k = 4, x = 3
【输出】[1,2,3,4]

2.2> 示例 2：

【输入】arr = [1,2,3,4,5], k = 4, x = -1
【输出】[1,2,3,4]

提示：

1 <= k <= arr.length
1 <= arr.length <= 10^4
arr 按升序排列
-10^4 <= arr[i]，x <= 10^4

三、解题思路

3.1> 思路1：中心点+前后指针

根据题目描述，我们可以知道其中有几个重要的信息。首先：这个数组arr是排序好了的，并且要求返回的结果也是排序的。那么，我们可以推测出来，最终的结果也就是原数组arr的一个子集。

那么，我们就可以先根据题目中给的查找值x，去确定一下所在数组arr的下标位置midIndex。但是在查找过程中，如果查找到了相同值还好办，如果没有查找到与x相同的值，那怎么办呢？这里我们可以通过x与数组arr中每个元素进行判断，如果我们第一次发现第i个元素大于等于x了，那么就说明，midIndex的值要么是i，要么就是i-1，具体取哪个值，我们可以通过判断i和i-1这两个元素与x的差值哪个小，我们就将midIndex指向该位置。

判断完毕midIndex的值之后，我们就可以以它为中心点，向左或者向右进行发散操作。最初我们可以创建两个变量，分别为开始索引startIndex和结束索引endIndex，最初这两个值与midIndex都是相同的。那么我们可以根据方法入参k（最终数组长度）来确定startIndex或endIndex要移动的次数，在每次移动操作之前，我们都要对比arr[startIndex - 1]和arr[endindex + 1]这两个元素，如果对比的结果是小于等于，那么startIndex向前移动一位，即：startIndex++；反之，如果对比的结果是大于，那么则endIndex向后移动一位，即：endIndex--；直到循环次数完毕，组装最终的结果作为方法的返回值。

上面就是具体的解题思路，下面我们依旧以一个例子来说明具体的执行步骤。我们假设arr数组为：arr=[0,1,1,1,2,3,6,7,8,9]，需要返回数组长度：k=9，需要查找的元素值为x=4。那么，首先，我们遍历arr，当遍历到元素6的时候，第一次满足x < arr[i]，那么我们对比元素6与它前一位元素3哪一个与x=4的差值最小，我们发现，元素3的差值更小，所以，我们指定midIndex=5（指向元素3的位置）。

然后，我们创建startIndex和endIndex，初始值就是midIndex的值，即：startIndex=endIndex=midIndex；然后在每次循环中，通过判断arr[startIndex - 1]和arr[endIndex + 1]这两个元素与x=4之前的差值，然后向更小差值的一放移动。当循环完毕后，最终结果的数组就是在arr数组中以startIndex为开始，以endIndex为结束的这段子集。具体操作如下图所述：

图解LeetCode——658. 找到 K 个最接近的元素（难度：中等）_后端

3.2> 思路2：排除无用元素

根据题意，逆向思考一下，其实我们不需要确定中间的元素在哪里，因为结果数组一定是连续的，所以只需要确定哪些元素对我们来说是“无用”的元素，然后将这些元素“排除在外”就可以了。

我们还是以arr数组为：arr=[0,1,1,1,2,3,6,7,8,9]，需要返回数组长度：k=9，需要查找的元素值为x=4为例。首先，我们确定要“排除”的元素有多少个，计算方式就是：arr.length - k = 10 - 9 = 1。我们只需要排除掉一个元素即可，那么我们设定开始索引位置startIndex=0，结束索引位置endIndex= arr.length -1; 然后计算一下，x与arr[startIndex] 和 x与arr[endIndex]那个差值更大，那么就将差值大的那个元素，排除在外即可。具体操作如下图所示：

图解LeetCode——658. 找到 K 个最接近的元素（难度：中等）_后端_02

四、代码实现

4.1> 代码1：中心点+前后指针

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int midIndex = 0; // 中心位置
        if (x <= arr[0]) return build(arr, 0, k, x);
        if (x >= arr[arr.length - 1]) return build(arr, arr.length - 1, k, x);
        for (int i = 0; i < arr.length; i ++) if (arr[i] >= x) return build(arr, (Math.abs(arr[i] - x)) >= (Math.abs(x - arr[i - 1])) ? i - 1: i, k, x);
        return new ArrayList();
    }

    public List<Integer> build(int[] arr, int midIndex, int length, int x) {
        int startIndex = midIndex, endIndex = midIndex;
        while(length > 1) {
            if ((endIndex >= arr.length - 1) || (startIndex > 0 && Math.abs(x - arr[startIndex - 1]) <= Math.abs(arr[endIndex + 1] - x))) startIndex--;
            else endIndex++;
            length--;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = startIndex; i <= endIndex; i++) result.add(arr[i]);
        return result;
    }
}

图解LeetCode——658. 找到 K 个最接近的元素（难度：中等）_Math_03

4.2> 代码2：排除无用元素

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int deleteNum = arr.length - k, startIndex = 0, endIndex = arr.length - 1;
        while (deleteNum > 0) {
            if ((x - arr[startIndex]) <= (arr[endIndex] - x)) endIndex--;
            else startIndex++;
            deleteNum--;
        }

        List<Integer> result = new ArrayList<>();
        for (int i = startIndex; i <= endIndex; i++) {
            result.add(arr[i]);
        }
        return result;
    }
}

图解LeetCode——658. 找到 K 个最接近的元素（难度：中等）_后端_04

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞 & 分享。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」

标签：endIndex,arr,int,元素,midIndex,startIndex,图解,LeetCode,658
From： https://blog.51cto.com/u_15003301/6330107