【每日一题】658. 找到 K 个最接近的元素

658. 找到 K 个最接近的元素 - 力扣（LeetCode）

给定一个 排序好 的数组 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
• arr 按 升序 排列
• -104 <= arr[i], x <= 104

class Solution {
    public List findClosestElements(int[] arr, int k, int x) {
        ArrayList ans = new  ArrayList();
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        while(left < right) {
            int mid = (left+right)/2;
            if(arr[mid]<=x) left = mid+1;
            else right = mid;
        }
        int front = left-1;
        int tail = left;
        for(int i = 0 ; i < k ; i++) {
            if(front < 0) {
                ans.add(arr[tail]);
                tail++;
            } else if(tail >= len) {
                ans.add(arr[front]);
                front--;
            } else {
                if(x-arr[front] <= arr[tail]-x) {
                    ans.add(arr[front]);
                    front--;
                } else{
                    ans.add(arr[tail]);
                    tail++;
                }
            }
        }
        Collections.sort(ans);
        return ans;
    }
}

        每日一题，今天是中等题。实际难度也不高。

        读题，升序排列，查找。二分查找能解决。题目要求找到离x距离最近的k个数。那首先要找到x或者离x最近的数。最简单的方法就是二分先找到离x最近的数。那就先写一个二分，找到距离大于x的第一个数。left，right，len，mid老几件安排上。出二分后，left就是大于x的第一个数，但我们要找的是距离x最近的几个数，有可能大于x也有可能小于x。所以，出来之后，使用front来记录小于等于x的半部分，tail来记录大于等于x的半部分。tail=left，front=left-1，同时要注意x不一定在数组里，所以front和tail有可能不是有效的下标。需要先进行判断：（1）如果front<0说明已经没有比x小的数了。（2）如果right>=len就说明没有比x大的数了。由于k一定有相应解，所以一旦front和tail中的一个越界了，就只能往另一边找，直接加数就行。（3）如果front和tail都有效，那么就要判断谁离x比较近，由于题目有距离相同时取小的要求，所以等号要加在front--的这一部分代码上。找到之后放进arraylist里面，返回之前对其进行排序即可。

        今天这道中等题也不怎么难，熟悉二分估计很快就能做出来。结果如下：