Description
給定已排序的整數陣列
arr、整數k和整數x，回傳最接近x的k個元素，以排序方式回傳。若兩個元素距離相同，較小的優先。
Example:
Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]
Intuition#
核心思路：結果一定是原陣列中連續的 k 個元素。用二分搜尋找到最佳的起始位置。
- 因為陣列已排序，最接近 x 的 k 個元素一定是連續的子陣列
- 可以用 Two Pointers 從兩端縮小，或用 Binary Search 找起始位置
- Binary Search 的搜尋目標：找到 left 使得
arr[left:left+k]最佳
Approaches#
1: Two Pointers（從兩端收縮）#
- 概念: 先取整個陣列，每次比較兩端哪個離 x 更遠，移除較遠的那端，直到剩下 k 個
- 時間複雜度:
O(n)- 最多移除 n-k 次 - 空間複雜度:
O(1)- 不計結果
class Solution {
fun findClosestElements(arr: IntArray, k: Int, x: Int): List<Int> {
var left = 0
var right = arr.size - 1
while (right - left + 1 > k) {
if (x - arr[left] <= arr[right] - x) {
right--
} else {
left++
}
}
return arr.slice(left..right)
}
}⭐2: Binary Search 找起始位置#
- 概念: 二分搜尋找起始索引
left（範圍[0, n-k]）。比較x - arr[mid]和arr[mid+k] - x決定搜尋方向 - 時間複雜度:
O(log(n-k) + k)- 二分 + 建立結果 - 空間複雜度:
O(1)- 不計結果
class Solution {
fun findClosestElements(arr: IntArray, k: Int, x: Int): List<Int> {
var left = 0
var right = arr.size - k
while (left < right) {
val mid = left + (right - left) / 2
// 比較視窗左端點和右端點之外的距離
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1
} else {
right = mid
}
}
return arr.slice(left until left + k)
}
}比較的是
x - arr[mid]和arr[mid+k] - x（注意是mid+k不是mid+k-1），因為我們在比較「是否應該把視窗右移」– 即把arr[mid]換成arr[mid+k]是否更好。
🔑 Takeaways#
- Pattern: Binary Search 找最佳視窗起始位置
- 關鍵技巧: 搜尋空間是起始位置
[0, n-k]；比較對象是arr[mid]與arr[mid+k]（視窗外下一個元素），決定視窗是否應該右移