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

第一章 数组 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;
    }
};