模版III - 找到 K 個最接近的元素（middle）
一、題目
LeetCode658.找到 K 個最接近的元素
給定一個排序好的陣列 arr ，兩個整數 k 和 x ，從陣列中找到最靠近 x（兩數之差最小）的 k 個數，回傳的結果必須要是按升序排好的，
整數 a 比整數 b 更接近 x 需要滿足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
示例 1：
輸入：arr = [1,2,3,4,5], k = 4, x = 3
輸出：[1,2,3,4]
二、基礎模版 III
因為我們的判斷區間最少為 2 個元素，所以我們要注意回圈的執行條件
- 簡單的判斷邊界：
nums.length === 0，return -1； - 定義初始的左右邊界：
left = 0, right = nums.length - 1； - 確定執行條件：
left + 1 < right，這也意味著查找區間要存在 3 個元素； - 向左查找時：
right = mid； - 向左查找時：
left = mid； - 判斷剩下的兩個元素哪個符合目標元素，并回傳結果；
三、題解
分析模版
- 我們的目標是：尋找目標值的起始下標和終止下標，但它是可能重復的
- 針對這樣的情況，我們要將判斷拆解成查找目標首次出現的位置，和最后一次出現的位置
JavaScript代碼
var findClosestElements = function(arr, k, x) {
let left = 0;
let right = arr.length - k; // 注意我們讓出來k的值，當作我們的“備用值”
let res = [];
while (left < right) {
let mid = left + ((right - left) >> 1);
if (x - arr[mid] > arr[mid + k] - x) {
// x-arr[mid] > arr[mid+k]-x，arr[mid+k]的點一定距離目標值更近
// 且它距離arr[mid]是k個，證明arr[mid]一定不會存在與結果區間中，它也不可能是起始點
left = mid + 1; // 我們在移動滿足條件的起始點
} else {
// x-arr[mid] <= arr[mid+k]-x，arr[mid]下標的點一定距離目標值更近
// 所以我們需要收縮右邊界
right = mid; // 壓縮右區間
}
}
for(let i = left; i < left + k; i++){
res.push(arr[i])
}
return res;
};
四、寫在最后
本文是二分查找-模版III 的第最后一題，我會在之后將二分法的常見問題整理成完成的檔案，我們一起加油～
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- JavaScript 版 LeetCode 題解
- 前端進階筆記
- CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/236604.html
標籤：其他
上一篇：python Django admin與xadmin后臺的問題報錯
下一篇：HTML+CSS仿BMW官網