【代码随想录】算法训练营 第一天 第一章 数组 Part 1

目录

数组基础知识补充

704. 二分查找

题目

左闭右闭方法

思路

代码

左闭右开方法

思路

代码

27. 移除元素

题目

暴力解法

思路

代码

双指针法

思路

代码

---

数组基础知识补充

1. 在leecode中，数组一般是以vector容器的形式出现的，虽然vector的底层实现是array，但严格来讲vector是容器，不是数组；

2. 数组元素的删除和增添都需要移动后续元素，而且在实现的角度上看，数组元素是不能删的，只能用后一个元素将其覆盖掉，然后再逐个覆盖，就相当于向前移动后续元素了；

3. C++二维数组的存储空间是连续的，但Java的不是，Java中每一个外层数组都会有指针指向内层数组的地址。

704. 二分查找

题目

左闭右闭方法

左闭右闭，意味着搜索区间是闭合的，比如 [ 1 , 5 ]，在这种区间搜索元素，两个指针指向同一个元素时一定是有意义的，因为区间涉及到的元素都在区间内；

但如果搜索区间是半开半闭的，那么就要考虑指针不能指向开的那个元素，需要对代码进行一定的改动。

思路

用二分查找来做这道题是高效且简单的，因为元素递增不重复；

闭合区间二分的思路是，分别给数组的最左边和最右边一个指针，每次通过求两个指针指向地址的中间处那个元素的值，来判断是否和目标值相等，相等的话就返回中间处的值的下标，不相等的话则分为两种情况：

如果中间处的值小于目标值，以为这中间处以及它的左边的元素都太小，所以接下来我们就把搜索区间的左边界缩到中间处右边一个的元素那里；

如果中间处的值大于目标值，同理就把搜索区间的右边界缩小到中间处左边一个的元素那里。

因为这里是一个闭区间，所以二分的终止条件就是两个指针指向相同，这时候如果指向的元素不等于目标值，那就返回 -1 。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1; 
        int mid = 0;
        while (l <= r) {
            mid = l + (r - l) / 2; // 防止l和r过大，直接相加越界
            if (nums[mid] == target)
                return mid;
            if (nums[mid] < target)
                l = mid + 1;
            else
                r = mid - 1;
        }
        // 带入一个有两个元素的数组测试样例就知道，如果我们的目标是后者，第一次的mid指向前面那个，后面的l加一以后就指向目标了，这时候l和r相等，mid也和它们相等了，可以得到结论；
        //如果没有在while条件中写=，那么l和r指向相同时就直接跳出循环了，这时候mid还未赋新值，就会出错
        return -1;
    }
};

左闭右开方法

思路

大体上和上面的方法一样，主要注意的是while的终止条件，这时候就不能是指针指向相同了，要把等于号去掉，因为区间边界一开一闭，两者显然是不能混为一谈的；

另外，开区间的那一边的搜索边界需要注意，如果mid指向的元素大于目标值，那么这时候将有边界缩小到mid即可，不用减一，具体见代码。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
         int l = 0, r = nums.size();
         while (l < r) {
             int mid = l + (r - l) / 2;
             if (nums[mid] < target)
                l = mid + 1;
            else if (nums[mid] > target)
                r = mid; // 这时候不能再写mid-1了，因为这是开区间，mid肯定不可能是目标值了，但是mid-1可能是，如果把mid-1赋值给r，那就意味着排除掉了mid-1
            else
                return mid;
         }
         return -1;
    }
};

27. 移除元素

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

暴力解法

思路

用内外两层指针，外层指针遍历数组并寻找和目标值相等的元素，找到以后使用内层指针遍历该元素之后的所有元素，将所有元素往前移动一位，其实就是用后一个元素将前一个元素覆盖掉；

其中有一些细节需要注意，首先是数组长度要实时记录，最后返回的就是数组长度，而且每次覆盖一轮后数组长度就减一了，所以外层指针相应地也要减一。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < size; j++)
                    nums[j - 1] = nums[j];
                i--;
                size--;
            } 
        }
        return size;
    }
};

双指针法

思路

使用一快一慢两个指针，用一个for循环完成两个for循环的任务。

首先定义一个慢指针，在此基础上再定义一个快指针在数组里从头扫到尾，如果遇见不等于目标值的数，就把这个数赋值给慢指针，相当于用慢指针创造了一个不包含目标值的新数组，但是这个新数组使用的就是原数组的空间。

代码

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; // 因为最后slow还有一个++，所以这里直接返回，不用+1
    }
};