题目描述

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

整数 a 比整数 b 更接近 x 需要满足：

• |a - x| < |b - x| 或者
• |a - x| == |b - x| 且 a < b

样例

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

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

限制

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• 数组里的每个元素与 x 的绝对值不超过 10^4

算法

(二分，双指针) $O(\log n + k)$

1. 使用二分，找到第一个大于等于 $x$ 的位置 $p_r$，若不存在则为 $p_r = n$，然后令 $p_l = p_r - 1$。
2. 然后开始向两侧扩展 $p_l$ 和 $p_r$，判断 $arr(p_l)$ 和 $arr(p_r)$ 谁更接近 $x$，移动 $p_l$ 或者 $p_r$，直到找满 $k$ 个数字为止。

时间复杂度

• 二分的时间复杂度为 $O(\log n)$，寻找答案的时间复杂度为 $O(k)$，故总时间复杂度为 $O(\log n + k)$。

C++ 代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        const int n = arr.size();
        vector<int> ans(k);

        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (x <= arr[mid]) r = mid;
            else l = mid + 1;
        }
        int pl = l - 1, pr = l;

        while (k--) {
            if (pl == -1) pr++;
            else if (pr == n) pl--;
            else {
                if (x - arr[pl] <= arr[pr] - x) pl--;
                else pr++;
            }
        }

        for (int i = pl + 1, j = 0; i < pr; i++, j++)
            ans[j] = arr[i];

        return ans;
    }
};