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

2023-12-27 22:56:11
第一章 数组 part01
?今日任务?

数组理论基础,704.?二分查找,27.?移除元素??

?详细布置
?数组理论基础??

文章链接:代码随想录

题目建议:?了解一下数组基础,以及数组的内存空间地址,数组也没那么简单。

?704.?二分查找?

题目建议:?大家能把?704?掌握就可以,35.搜索插入位置?和?34.?在排序数组中查找元素的第一个和最后一个位置?,如果有时间就去看一下,没时间可以先不看,二刷的时候在看。

先把?704写熟练,要熟悉?根据?左闭右开,左闭右闭?两种区间规则?写出来的二分法

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:代码随想录

视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili

?27.?移除元素

题目建议:??暴力的解法,可以锻炼一下我们的代码实现能力,建议先把暴力写法写一遍。?双指针法?是本题的精髓,今日需要掌握,至于拓展题目可以先不看。?

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:代码随想录

视频讲解:数组中移除元素并不容易! | LeetCode:27. 移除元素_哔哩哔哩_bilibili


? ? ? ? 对于这个题,满足数组有序,使用左闭右开写法实现

c/c++代码示例如下:

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

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


?????????显然暴力法就是遍历数组,当nums[i]==val时,从下标i+1开始所有元素前移一位,并将len-1。(补充:i要及时回溯)

代码示例如下:

int removeElement(int* nums, int numsSize, int val) {
    int len=numsSize;
    for (int i=0;i<numsSize-1;i++){
        if (nums[i]==val){
            for (int j=i+1;j<numsSize;j++){
                nums[j-1]=nums[j];
            }
            len--;
            i--;
        }
    }
    return len;
}

这个代码中注意i的回溯,若i不回溯,出现连续val就wa了。时间复杂度O(n^2)。

? ? ? ? 优化一下可以这样做:(双指针法-左右指针)

初始化左指针i为数组首,右指针j为数组尾。分别用循环来模拟左指针右移,右指针左移:左指针在nums[i]==val时停下,右指针在nums[j]!=val时停下。然后直接用右指针指向元素覆盖左指针指向元素,当左右相错结束循环,左指针一定指向最终数组尾

代码示例如下:

int removeElement(int* nums, int numsSize, int val) {
    int pl=0,pr=numsSize-1;
    while (pl<=pr){
        while (pl<=pr&&nums[pl]!=val){
            pl++;
        }
        while (pl<=pr&&nums[pr]==val){
            pr--;
        }
        if (pl<pr){
            nums[pl++]=nums[pr--];
        }
    }
    return pl;
}

还有问题:不取等的话,在相遇时结束循环在[]情况时不对

其他录友的方法:

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

还有快慢指针法

// 时间复杂度: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;
    }
};

文章来源:https://blog.csdn.net/2302_79277225/article/details/135231594
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。