代码随想录Day1 | 数组01- leetcode 704、27-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录Day1 | 数组01- leetcode 704、27。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

704-二分法

题目链接：二分查找

关键问题：

- 边界（left、right）、当前查找值（middle）

- target大于当前查找值 --> 当前查找区域的右边，更改区间left

- target小于当前查找值 --> 当前查找区域的左边，更改区间right

- middle的计算：（right - left）/2 + left

- 查找区间

- 开区间or闭区间 --> 涉及while的判断条件即target不存在的情况

时空复杂度：

- 时间复杂度：数组长度为n，查找区间的长度：n、n/2、n/4、n/8、...、n/2^k --> O(log n)

- 空间复杂度：O(1)

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while(left <= right){
            int middle = left + ((right - left)/2);
            if(nums[middle] == target){
                return middle;
            } else if(nums[middle] > target){
                right = middle - 1;
            } else{
                left = middle + 1;
            }
        }

        return -1;
    }
};

一些可以提升性能的细节：在三个if判断中，将查找到结果放在最前(代码第9-10行) --> 若当前命中则可以减少两次判断

27- 移除元素

题目链接：移除元素

1. 暴力解法

算法描述：当查找到每一个待删除元素，都将所有后续元素向前移动一次

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 暴力解法 --> 所有元素前移
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(nums[i] == val){
                for(int j = i; j < n-1; j++){
                    nums[j] = nums[j+1];
                }
                i--;
                n--;
            }
        }
        return n;
    }
};

代码细节（i--）： 由于发生了前移，当前位置i发生了元素的替换，而i在循环中自增，因此需要i--，回到位置i处。

时间复杂度：

2.快慢指针

算法描述：双指针法，快慢指针同时从头遍历，遇到待移除元素时慢指针停止，快指针继续移动直到遇到第一个不需要移除的元素，此时将快指针指向的元素拷贝到慢指针指向的数组位置，拷贝完成后，快慢指针继续同步移动，直至快指针遍历完数组。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //快慢指针
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++){
            if(nums[fast] != val){
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

时间复杂度：O(n)

3.相向双指针

算法描述：双指针法，设置首尾指针，首指针开始遍历，当遇到待移除元素时停止，此时尾指针从后向前移动至不需要删除的元素位置处，将尾指针指向的元素拷贝到首指针指向的位置，尾指针前移一步。首指针继续遍历，遇到待移除元素重复上述操作，直至首位指针相遇。

优点：与快慢指针对比来考虑，若遇到待删除元素在靠前位置时，快慢指针需要移动所有后续元素，而双向双指针只需要一次替换操作。举例来说：对于数组A[n] = [0,1,1,...,1,1,2]，当需要删除元素0时，快慢指针需要移动0后续的所有元素，得到的结果为A[n-1] = [1,1,...,1,1,2]，而相向双指针仅需一次替换将2替换到最前，得到的结果为A[n-1] = [2,1,1,...,1,1]。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 相向双指针
        int left = 0;
        int right = nums.size() -1;
        
        while(left <= right){// 闭区间
            if(nums[left] == val){
                if(nums[right] != val){
                    nums[left] = nums[right];
                    left++;
                }
                right--;
            }else{
                left++;
            }
        }
        return left;
    }
};

时间复杂度：O(n)文章来源地址https://www.toymoban.com/news/detail-589111.html

到了这里，关于代码随想录Day1 | 数组01- leetcode 704、27的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！