代碼随想錄day1 打卡

• 數組
• • 數組理論基礎
  • 704二分查找
  • 27移除元素

數組

數組理論基礎

704二分查找

//二分查找架構
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}
           

分析二分查找的一個技巧是：不要出現 else，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現所有細節。

其中 … 标記的部分，就是可能出現細節問題的地方，當你見到一個二分查找的代碼時，首先注意這幾個地方。後文用執行個體分析這些地方能有什麼樣的變化。

另外提前說明一下，計算 mid 時需要防止溢出，代碼中 left + (right - left) / 2 就和 (left + right) / 2 的結果相同，但是有效防止了 left 和 right 太大，直接相加導緻溢出的情況。

題目連結：704二分查找

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while(left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        }
    }
    return -1;
};
           

1、為什麼 while 循環的條件中是 <=，而不是 <？

答：因為初始化 right 的指派是 nums.length - 1，即最後一個元素的索引，而不是 nums.length。

這二者可能出現在不同功能的二分查找中，差別是：前者相當于兩端都閉區間 [left, right]，後者相當于左閉右開區間 [left, right)，因為索引大小為 nums.length 是越界的。

我們這個算法中使用的是前者 [left, right] 兩端都閉的區間。這個區間其實就是每次進行搜尋的區間。

什麼時候應該停止搜尋呢？當然，找到了目标值的時候可以終止：

if(nums[mid] == target)
	return mid; 
           

但如果沒找到，就需要 while 循環終止，然後傳回 -1。那 while 循環什麼時候應該終止？搜尋區間為空的時候應該終止，意味着你沒得找了，就等于沒找到嘛。

while(left <= right) 的終止條件是 left == right + 1，寫成區間的形式就是 [right + 1, right]，或者帶個具體的數字進去 [3, 2]，可見這時候區間為空，因為沒有數字既大于等于 3 又小于等于 2 的吧。是以這時候 while 循環終止是正确的，直接傳回 -1 即可。

while(left < right) 的終止條件是 left == right，寫成區間的形式就是 [right, right]，或者帶個具體的數字進去 [2, 2]，這時候區間非空，還有一個數 2，但此時 while 循環終止了。也就是說這區間 [2, 2] 被漏掉了，索引 2 沒有被搜尋，如果這時候直接傳回 -1 就是錯誤的。

2、為什麼 left = mid + 1，right = mid - 1？我看有的代碼是 right = mid 或者 left = mid，沒有這些加加減減，到底怎麼回事，怎麼判斷？

答：這也是二分查找的一個難點，不過隻要你能了解前面的内容，就能夠很容易判斷。

剛才明确了「搜尋區間」這個概念，而且本算法的搜尋區間是兩端都閉的，即 [left, right]。那麼當我們發現索引 mid 不是要找的 target 時，下一步應該去搜尋哪裡呢？

當然是去搜尋區間 [left, mid-1] 或者區間 [mid+1, right] 對不對？因為 mid 已經搜尋過，應該從搜尋區間中去除。

3、此算法有什麼缺陷？

答：至此，你應該已經掌握了該算法的所有細節，以及這樣處理的原因。但是，這個算法存在局限性。

比如說給你有序數組 nums = [1,2,2,2,3]，target 為 2，此算法傳回的索引是 2，沒錯。但是如果我想得到 target 的左側邊界，即索引 1，或者我想得到 target 的右側邊界，即索引 3，這樣的話此算法是無法處理的。

這樣的需求很常見，你也許會說，找到一個 target，然後向左或向右線性搜尋不行嗎？可以，但是不好，因為這樣難以保證二分查找對數級的複雜度了。

我們後續的算法就來讨論這兩種二分查找的算法。

27移除元素

題目連結：27移除元素

function removeElement(nums, val) {
    //暴力解法
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) {
            nums.splice(i, 1);
            i--;
        }
    }
    return nums.length;
}
           

function removeElement(nums, val) {
    //雙指針
    let i = 0;
    for (let j = 0; j < nums.length; j++) {
        if (nums[j] !== val) { //如果不等于val，就把j的值賦給i
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}
           

類似 26. 删除有序數組中的重複項 中的快慢指針：

如果 fast 遇到需要去除的元素，則直接跳過，否則就告訴 slow 指針，并讓 slow 前進一步。