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

1 数组

1.1 数组理论基础

数组的特点：

• 数组是存放在连续内存空间上的相同类型数据的集合（数组内存空间的地址是连续的）

  • 带来的缺点：正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

• 数组可以方便的通过下标索引的方式获取到下标下对应的数据（数组下标都是从0开始的）

• 数组的元素是不能删的，只能覆盖。

二维数组特点：

• C++中二维数组在地址空间上是连续的

• Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机（根据输出的地址可以看出，这不是真正的地址，而是经过处理过后的数值了，我们也可以看出，二维数组的每一行头结点的地址是没有规则的，更谈不上连续）

1.2 二分查找

数组查找使用二分法的前提：

1. 数组是有序的

2. 数组中没有重复元素

区间定义：一般区间定义的都是左闭右闭或者左闭右开；区间定义可以理解为是不变量，一开始定义好了，接下来在循环中的处理要坚持这个原则（左闭右闭还是左闭右开）

易错点：

1. 迭代法中while的条件

2. right=mid还是mid-1

先以左闭右闭来写这个代码，首先得是right被赋值为size-1，那么while中的条件是小于还是小于等于呢，因为是左闭右闭的，所以等于这个条件是合法的，所以得写；对于right应该是mid-1还是等于mid，因为mid已经判断过了，所以不用包含，是mid-1

再以左闭右开为例，首先得是right被赋值为size，如果定义成左闭右开，那么while中的条件如果相等的话，那它就不是一个合法的区间，所以不能有等于，然后同理right等于mid就行，因为是左闭右开所以不会包含mid，left得是mid+1

• 时间复杂度：O(log n)

• 空间复杂度：O(1)

1.3 27移除元素

这个题看起来简单，但是比较考验对数组的底层实现的一些理解

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖

需要注意的是在数组中，删掉一位元素，就是要把它之后的元素往前移把要删的元素覆盖掉，这个数组真正的在内存空间中的大小没变，只不过一些编程语言会对数组进行一层包装，例如：C++中的vector，Java、python等都会提供各式各样数组里面的接口（时间复杂度其实是O(n)的），删除一个元素之后，返回的size就会变小一个，但并不代表这个空间真正地变小了，而是其中有一个计数器，调用函数之后默认做了一个减减的操作

什么时候使用库函数？如果一个题目用库函数能一行代码解决，那就不要用库函数做，很明显不是在考察我们的代码能力

这个题目其实就是让我们实现一下erase函数删除元素的过程

方法一：暴力求解法：使用两层for循环

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

class Solution {
    public int removeElement(int[] nums, int val) {
        //暴力法：遍历查找，找到后移动到最后一位
        // int temp=0;
        int len=nums.length;
        for(int i=0;i<len;i++){
            if(nums[i]==val){
                // temp=nums[i];
                for(int j=i;j<len-1;j++){
                    nums[j]=nums[j+1];
                }
                // nums[nums.length-1]=val;
                len--;
                i--;
            }
            
        }
        return len;
    }
}

暴力求解法易错点：

1. 只需要管“所求长度”内的元素就行，之外的元素长什么样不用管，所以赋值的这一步// nums[nums.length-1]=val;不需要有（加上可能是对的，但是力扣中显示超过时间限制，所以无法判断）

2. 很巧妙的一点是，因为只需要管“所求长度”内的元素就行，之外的元素长什么样不用管，所以执行len--;（因为i之后的元素都先前移动了一位后，最后一个元素就不用管了；len--;不执行或许也可以，但是超过力扣的时间限制）

3. 需要注意的是，在把i之后的元素向前移动之后，i本身的值也变了，但是此时还没有对新的i的值进行判断，所以i--;需要被执行

方法二：双指针法

注意一定要搞清楚两个指针各自的含义

在本题中：定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组

• 慢指针：指向更新 新数组下标的位置

• 时间复杂度：O(n)

• 空间复杂度：O(1)

自己的写法：

class Solution {
    public int removeElement(int[] nums, int val) {
        //双指针法
        int len=nums.length;
        int left=0;
        int right=len-1;
        int temp=0;
​
        while(left<=right){
            if((nums[left]==val)&&(nums[right]!=val)){
                temp=nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
                len--;
                left++;
                right--;
            }else if((nums[left]!=val)&&(nums[right]!=val)){       
                left++;
            }
            else if((nums[left]!=val)&&(nums[right]==val)){
                left++;
            }else{
                len--;
                right--;
            }
            
        }
        return len;
    }
}

双指针思路（卡哥）：O(n)的方式就能实现，这个方法其实是用一层for循环做了两层for循环做的事情；把快指针的值赋给慢指针之后，慢指针也应该加加

nums[slowIndex++] = nums[fastIndex];

先赋值，再对里面的变量加加

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow=0;
        for(int fast=0;fast<nums.length;fast++){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
                // fast++;
            }
        }
        return slow;
    }
}

双指针法的思考：在没有找到val之前，slow和fast都是指向同一个位置的，会有赋值，不过其实是自己等于自己，然后slow和fast同步加加；直到遇到val，slow就不能动了，fast要继续移动来找到非val的值进行覆盖，slow后面有可能都是val，也可能都是非val，也可能都有；如果都是非val，那fast的值又继续赋给slow，slow和fast又同时开始加加，不过它们之间一直错开几个值（fast遇到的非val的位置和slow位置的差）；如果后面有val也有非val，移动覆盖后又成了前面讨论过的子问题

如果一整个问题太大太复杂很难想，拆成不同的小情况分别讨论，这几个小情况分别都满足就行，不一定要一起满足

或许太简化的代码看不懂，可以看看扩充之后的