LeetCode 658、找到 K 个最接近的元素

1）题目描述

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

2）分析

双指针。

• 要求的K个数在数组中一定是连续的；
• 从数组的数位向中间寻找，直到两指针之间只有K个元素；
• 比较的条件 x − a r r [ l e f t ] > a r r [ r i g h t ] − x x-arr[left]>arr[right]-x x−arr[left]>arr[right]−x 时，左指针右移一步，否则右指针左移一步。

3）C++代码

class Solution {
public:
    vector findClosestElements(vector& arr, int k, int x) {
        int left=0;
        int right=arr.size()-1;
        vector res;
        while(right-left>=k){
            if(x-arr[left]>arr[right]-x)
                left++;
            else
                right--;
        }
        while(left<=right)
            res.push_back(arr[left++]);
        return res;
    }
};