題目網址：https://leetcode.cn/problems/find-k-closest-elements/

題意：給一已排序的 array arr 以及兩整數 k 和 x, 從 arr 中找到最接近 x 的 k 個數。返回的 array 必須是已排序好的。

整數 a 比整數 b 更接近 x 須滿足：

  • |a - x| < |b - x|（a 比 b 更靠近 x） 或
  • |a - x| == |b - x| 且 a < b（兩者到 x 的距離相等, 但 a 比 b 小）

Solution 1：

想法：由於 arr 是有序的, 所以最後返回的 k 個元素也一定是有序的, 其實就是返回了原 array 中的一個長度為 k 的 subarray。實際上相當於在長度為 n 的 array 中去掉 n - k 個數字, 而且去掉的順序肯定是從兩頭開始, 因為距離 x 最遠的數字肯定在首尾出現。

➔ 每次比較首尾兩個數字跟 x 的距離, 並刪除距離較大的數字, 直到剩餘的 array 長度為 k 為止

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        while (arr.size() > k) {
            if (x - arr.front() <= arr.back() - x) {
                arr.pop_back();
            } else {
                arr.erase(arr.begin());
            }
        }
        return arr;
    }
};
  • time：$O(n-k)$ ➔ while loop, 其中 n 為 arr.size()
  • space：$O(1)$ ➔ 扣除要返回的 array, 只需常數空間

Solution 2：

想法：利用移動 window, 從位置 i 開始延伸出去的長度為 k 的 window(其中 0 ≤ i ≤ n-k)

以下圖為例, nums = [1,2,3,4,5], 其中每個不同顏色的框代表不同的 window

➔ 利用 Binary Search, 算出 mid 後, 先看最左邊元素為 mid 的 window, 然後其右邊一個的 window 進行比較

e.g. 圖中, mid = 2, 故當前 window 為藍框的 [3,4], 右邊一個的 window 為紫框的 [4,5]

透過比較 arr[mid] 及右邊一個的 window 中最右的元素 arr[mid + k] 來決定要往哪繼續做 Binary Search

e.g. 透過上例, 比較 3 和 5 來決定要縮小左邊界 or 右邊界

由於 5 比較接近 x = 5, 故往右走(右半邊剩下的 window 繼續做 Binray Search)

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - k;

        while (left < right) {
            const int mid = left + (right - left) / 2;

            // 比較 arr[mid] 和右邊一個 window 中最右的元素哪個比較接近 x
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return vector<int>(arr.begin() + left, arr.begin() + left + k);
    }
};
  • time：$O(log(n) + k)$
    • $O(log(n))$：binary search
    • $O(k)$：建立返回的 array
  • space：$O(1)$ ➔ 扣除要返回的 array, 只需常數空間