題目描述:給定一個已升序排序的整數陣列 arr,以及整數 k 和 x。回傳陣列中距離 x 最近的 k 個元素,結果須升序排列。若兩元素距離 x 相等,取值較小者(即較靠左者)。
解題思路(二分搜尋左起點):
答案是 arr 中一段長度為 k 的連續子陣列 arr[left..left+k-1]。因此問題轉化為:找最優的左起點 left。
左起點的搜尋範圍為 [0, n-k](確保有 k 個元素可取)。
比較法則:對於候選左起點 mid,比較「窗口左端 arr[mid] 距 x 的距離」與「窗口右端下一個 arr[mid+k] 距 x 的距離」:
x - arr[mid] > arr[mid+k] - x:左端點離 x 更遠,窗口應右移,故 left = mid + 1。x - arr[mid] <= arr[mid+k] - x):右端點離 x 更遠或相等,應保留當前或更左的窗口,故 right = mid。等距處理:條件中使用 > 而非 >=,使得等距時偏向取較小值(即保留 arr[mid]),符合題目要求。
終止:left == right 時即為最優左起點,返回 arr[left..left+k-1]。
時間複雜度:O(log(n - k) + k) — 二分搜尋在長度 n-k 的範圍內執行,需 O(log(n-k)) 次迭代;建立結果陣列需 O(k);整體 O(log(n-k) + k)。若 k 相對 n 較小,接近 O(log n);若需要 O(1) 空間(直接回傳迭代器範圍),則純搜尋部分為 O(log(n-k))。
空間複雜度:O(1)(不計輸出陣列)— 二分搜尋過程僅使用常數額外空間。
Function findClosestElements(arr, k, x):
n = length of arr
left = 0
right = n - k // valid left endpoints: [0, n-k]
While left < right:
mid = left + (right - left) / 2
// Compare distance of window's left end vs. element just outside right end
If (x - arr[mid]) > (arr[mid + k] - x):
left = mid + 1 // left end too far, shift window right
Else:
right = mid // right end farther (or equal), keep current or go left
// left == right: optimal starting index found
Return arr[left .. left+k-1]最大堆 O(n log k):遍歷陣列,維護大小為 k 的最大堆,按距離 x 的遠近排序(若距離相等按值排序)。每次新元素比堆頂更近時彈出堆頂並插入新元素。最後堆中的 k 個元素即為答案,需排序輸出。時間 O(n log k),比二分搜尋慢,但不需要陣列已排序。
兩指針(已排序陣列)O(n):先用二分找到最接近 x 的位置,然後用兩指針分別向左右擴展,每次取距離較近的方向。適合不需考慮等距選左的簡化版本,但處理邊界與等距邏輯較繁瑣。
直接二分 + 窗口 O(log n + k):先用 lower_bound 找到 x 的插入位置,然後以此為中心雙指針向外擴展取 k 個最近元素。邏輯直觀,但實作時需小心索引越界及等距比較的一致性。