代码随想录算法训练营第1天 | 704. 二分查找、27. 移除元素

发布于 2022-11-19  371 次阅读


AI 摘要

这篇文章介绍了算法训练营中的两道题目:704. 二分查找、27. 移除元素。对于二分查找的问题,文章给出了时间复杂度和空间复杂度都为O(log2n)的AC代码,并且与标准答案一模一样。而对于移除元素的问题,文章给出了两份AC代码,其思路为把左边要剔除的数字和最末尾的数字做交换,并且对于右边的指针需要-1以重新判定。作者也提到了代码中加特判和去特判的区别,以此提醒大家进行清晰的思路梳理。

704. 二分查找 - 力扣(LeetCode)

思路:看到这道题第一眼的想法是暴力解,但看了一眼标题,又想起来自己一年前曾经写过这题,当时用暴力解超时了,于是就想着用二分查找,没想到居然和标准答案一模一样哈哈哈

时间复杂度O(log2n) 空间复杂度O(1)

我的AC代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int r = nums.size() - 1;
        int l = 0;
        while(l <= r) {
            int loc = (l + r) / 2;//要学习一下新算法, loc = l + ((r - l) / 2), 这样可以防止溢出
            if(target == nums[loc]) {
                return loc;
            }
            else if(target >= nums[loc]) {
                l = loc + 1;
            }
            else if(target < nums[loc]) {
                r = loc - 1;
            }
        }
        return -1; 
    }
};

标准答案

// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
        while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间,所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

提交记录

提交记录

27. 移除元素 - 力扣(LeetCode)

思路:看到题目就想到了大致思路,但是由于太久没打代码了,在边界处思考了很久,同时又因为思路不够清晰导致初版代码没有过全部测试点,挂掉的测试点是

[1]
1
应该输出[]

于是加了特判

在这个测试点

[2,2,2]
2
应该输出[]

又挂了

后面仔细想了一下,其实思路就是把左边要剔除的数字和最末尾的数字做交换,如果和最后的数字一样,那么右边的指针-1,同时左边的指针也要-1,因为循环结束会+1,此处做-1是为了让它重新判定一次,如果和最末尾的数字不同才做交换,此时交换完毕后,右指针要-1,改完代码以后,AC了,把特判去掉,还是AC,故此放两个代码,第一个是有特判的,第二个是无特判的,其实有无特判不影响结果,以此为戒,思路一定要清晰!!!

我的AC代码1

// 时间复杂度O(n) 空间复杂度O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cnt = nums.size();
        int r = cnt - 1;
        if (0 == cnt) {
            return 0;
        }
        if(1 == cnt) {
            if(nums[0] == val) {
                return 0;
            }
            else {
                return 1;
            }
        }
        for(int l = 0; l <= r; ++l) {
            if(val == nums[l]) {
                if(nums[l] == nums[r]&& l != r) {
                    --r;
                    --l;
                }
                else {
                    int t = nums[l];
                    nums[l] = nums[r];
                    nums[r] = t;
                    --r;
                }
            }
        }
        return r + 1;
    }
};

我的AC代码2

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cnt = nums.size();
        int r = cnt - 1;
        for(int l = 0; l <= r; ++l) {
            if(val == nums[l]) {
                if(nums[l] == nums[r]&& l != r) {
                    --r;
                    --l;
                }
                else {
                    int t = nums[l];
                    nums[l] = nums[r];
                    nums[r] = t;
                    --r;
                }
            }
        }
        return r + 1;
    }
};

不过感觉最优美的做法还是标准答案的快慢指针

快慢指针的话,快指针是遍历者,而慢指针是收集者,遍历者会遍历整个数组,判断遇到的每一个元素,如果遇到的元素不是我们要的,就略过,如果遇到的元素是我们要的,就让慢指针,即收集者来收集,slowIndex++我认为比较传神,因为不仅精简了语句,在最后一次运行的那个slowIndex++还可以让我们返回的slowIndex++就是完成剔除以后的数组长度

标准答案

// 快慢指针法
// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};