解題程式碼

Two pointers(此解法更簡單好懂)

var findClosestElements = function (arr, k, x) {
  let l = 0;
  let r = arr.length - 1;

  while (r - l >= k) {
    if (Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) {
      r--;
    } else {
      l++;
    }
  }
  return arr.slice(l, r + 1);
};

之前做的時候，忘記在 while ((r - l) >= k) 那行加上等號，沒加的話等到長度等於 k 時就會結束循環了，有些 test case 會報錯，ex: [0,0,0,1,3,5,6,7,8,8]，k = 2, x = 2，所以要加上等號，

例如當 l = 2，r = 3，時，Math.abs(0 - 2) > Math.abs(1 - 2)，l = 3，r = 3，跳出 while，輸出時，將 r + 1，return arr.slice(l, r + 1)，結果為 [1,3]。

二元搜尋

var findClosestElements = function (arr, k, x) {
  // search left boundary
  let l = 0;
  let r = arr.length - k;

  while (l < r) {
    let mid = Math.floor((l + r) / 2);
    if (x - arr[mid] > arr[mid + k] - x) {
      // if 成立，意味 mid 離 x 較遠
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return arr.slice(l, l + k);
};

解題思路、演算法

這題可以有好幾種解法，以下分別說明:

話說這題在 Grind 169 上歸類在 Heap，結果查了很多解法都沒看到用 Heap 解 XDD

Two pointers

把 arr 的第一個元素和最後一個元素帶入 |a - x| <= |b - x| 的公式內，如果符合公式就保留 a，也就是 arr 前面的元素，移除 b，反之保留 b，移除前面的 a。是比較簡單的寫法。

參考 leetcode 中文 | Find K Closest Elements | Facebook 臉書面試題 | Leetcode 658 | Python

二元搜尋

參考 贾考博 LeetCode 658. Find K Closest Elements，兩個二分搜尋組在一起使用。

又或是維護一個 Sliding Window，middle 為 l 和 r pointer 的中間點，初始如下:

[1, 2, 3, 4, 5]，x = 5, k = 2
 l  m     r

經過公式 if ((x - arr[m]) > arr[m + k] - x) 檢查: Math.abs(4 - 5) = 1，Math.abs(5 - 2) = 3，4 比較近，移動 l pointer

[1, 2, 3, 4, 5]
       l  r
       m

經過公式檢查: Math.abs(5 - 5) = 0，Math.abs(3 - 5) = 2，5 比較近，移動 l pointer

[1, 2, 3, 4, 5]
          r
          l

參考 Find K Closest Elements - Leetcode 658 - Python

解法的時間、空間複雜度

時間複雜度: Two pointers O(n - k)，二元搜尋 O(log n + k)
空間複雜度: Two pointers O(1)，二元搜尋 O(1)

參考資料

LeetCode in Python 658. Find K Closest Elements (Medium)｜ Array ｜ Binary Search (解法 3/3) - Michelle 小梦想家