代码随想录算法训练营Day01 | LeetCode704 二分查找、Leetcode27 移除元素

今日学习的视频和文章

• 代码随想录数组基础 复习基础知识
• 代码随想录 二分查找
• 代码随想录 移除元素

LeetCode704 二分查找

题目链接：704. 二分查找 - 力扣（Leetcode）

以前学二分查找的时候，真的一直搞不清楚怎么操作左边界和有边界，以及循环的终止条件是什么，总是自己慢慢调试出来，然后下一次又忘了。直到看见了 Carl 哥的讲解，让我有种醍醐灌顶的感觉。不仅是二分查找，写其他算法的时候，记得循环不变量原则也让我的思路清楚很多。

循环不变量原则，在 while 中每一次对边界的操作都要严格遵循区间的定义来操作，区间的定义就是循环不变量。

左闭右闭区间

• 初始化，区间的定义为左闭右闭区间，即[l, r]。

那么应该这样初始化：

int l = 0;
int r = nums.size() - 1;//r能取等号，所以应该是数组nums的最大下标
int mid = (l + r) / 2;

• 考虑边界条件，l == r 时左闭右闭区间[l, r]是合理的，所以while语句的循环条件应为：

while (l <= r) {
    /* 二分查找 */
}

• 若target < nums[mid]，即target落在左边区间，nums[mid]已经被查找过，所以调整右边界r时，应该不包括mid。

while (l <= r) {
    if (target < nums[mid]) {
        r = mid - 1;
    }
    /* ... */
}

• 若nums[mid] < target，即target落在右边区间，nums[mid]也已经被搜索过，所以调整左边界时，也不应该包括mid。

while (l <= r) {
    if (target < nums[mid]) {
        r = mid - 1;
    }
    else if (nums[mid] < target) {
        l = mid + 1;
    }
}

• 若nums == target，即找到目标，直接返回mid即可。

• 综合以上分析得到完整题解代码：

int search(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size() - 1;
    int mid = (l + r) / 2;
    while (l <= r) {
        if (target < nums[mid]) {
            r = mid - 1;
        }
        else if (nums[mid] < target) {
            l = mid + 1;
        }
        else {
            return mid;
        }
        mid = (l + r) / 2;
    }
    return -1;
}

左闭右开区间

• 初始化，左闭右开区间[l, r)。则r = nums.size()。

int l = 0;
int r = nums.size();
int mid = (l + r) / 2;

• 考虑边界条件，对于左闭右开区间[l, r)而言，l == r是不合理的，所以while的循环条件应为l < r。
• 调整左边界时，mid是被搜索过的，l可以取等号，所以不应该包括mid，即l = mid + 1
• 调整右边界时，mid被搜索过，r不能取等号，正好将mid赋值给r，下一次循环的搜索范围正好不包括现在的mid。如果r = mid - 1，下一次循环的区间为[l, mid - 1)，少包含了nums[mid - 1]这个元素，显然逻辑是有问题的。

左闭右开区间的完整题解代码。

int search(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size();
    int mid = (l + r) / 2;
    while (l < r) {
        if (target < nums[mid]) {
            r = mid;
        }
        else if (nums[mid] < target) {
            l = mid + 1;
        }
        else {
            return mid;
        }
        mid = (l + r) / 2;
    }
    return -1;
}

LeetCode27 移除元素

暴力解法

• 暴力解法，先移除元素，再让未移除的元素把空位补上。

int removeElement(vector<int>& nums, int val) {
    int n = nums.size();
    int del = 0;
    for (int i = 0; i < n - del; i++) {
        if (nums[i] == val) {
            int j = i;
            while (j + 1 < n) {
                nums[j] = nums[j + 1];
                j++;
            }
            del++;
            i--;//这里要注意判断下一个元素是否等于 val，否则可能会漏掉 val 的元素
        }
    }
    return n - del;
}

以上算法的时间复杂度为O(n^2)

双指针法（快慢指针法）

• 删除数组元素本质是用后面的元素覆盖前面的元素，让元素在空间上保持连续分布。那么，只需要判断哪个元素保留，哪个元素被覆盖，就可以在一次遍历中完成删除数组元素。
• 用slow指针指向要被覆盖的元素位置，用fast指针表示当前遍历到的元素的位置。在遍历数组时，用nums[fast]给nums[slow]赋值。
  1. 当fast指向要删除的元素时，fast直接+ 1而不用 nums[fast] 给 nums[slow] 赋值，此时fast已经跳过了要被删除的元素。
  2. 然后，当 fast 指向不会被删除的元素时，用nums[fast]给nums[slow]赋值，此时，被保留的元素覆盖了要被删除的元素的位置，完成了一个元素的删除，并且保持了元素在空间上的连续分布。

完整题解代码如下：

int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int fast = 0;
        int slow = 0;
        for (;fast < n; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return n - fast + slow;
    }
};