数组题目复习Day1

704二分查找

自己看到题目的第一想法 暴力O(n)全部遍历一遍，这个数据量还可以，但是再大一点就会特别慢

二分法O(logn)，左右指针控制大小范围

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

    }
};

一开始只写了right/2，导致一直在超时（真的要嘲笑一下自己的脑子）

后来只剩下两个样例未通过left==right=0这样的条件下target==nums[0]/target!=nums[0]，找边界值非常费劲！打了各种补丁，while里面的条件多加了个=，多加了第三个if条件

这样的代码也太不优雅了，一点规范和逻辑都没有，于是我必须学习卡哥的代码了！

看完视频和随想录：我直呼nb

难点有二：①while的循环条件是否需要=? ②middle下标是(left+right)/2-1还是不-1？ 一定要先清楚left和right范围是否包括边界值，常见的有左闭右闭(包括left和right)，左闭右开(包括left不包括right)

左闭右闭考虑

难点①：等于是合法条件，比如[1]这样的数组，一定要记住是左闭右闭，left==right=0合法，因此需要加上等号

难点②：if条件是中间值大于目标值 right = middle-1;，一定要逻辑清晰，既然条件当中的中间值大于目标值了，那么中间值一定不是了，由于我们是右闭，right就不能落在middle上；同理条件是中间值小于目标值left = middle+1;；等于middle直接返回就可以了，搜到最后也没有就返回-1。

另外值得一提的是，注意初始的right值也需要明晰是右闭还是右开，右闭就是size()-1，右开就是size()

那么开撕！

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

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

卡哥的代码还做了找中间值时防止溢出的操作，实在是细节middle = left+(right-left)>>1;

时长：自己写了30min

听视频讲解15min，重新手撕两个版本共10min

27移除元素

没看任何材料的解法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cnt = 0;
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            if(val!=nums[i]){
                cnt++;
            }
            else{
                nums[i] = 101;
            }
        }
        int l = nums.size();
        sort(nums.begin(),nums.end());
        return cnt;
    }
};

复杂度O(nlogn)

这简直就是挨打写法，不过要是真暴力，里面就要再循环覆盖掉O(n^2)，但我觉得应该不是这样，说是移除，但是绝对不是物理意义上的移除，我会想到双指针，但是不太会写，也不知道是不是这个思想。

双指针解法

都在一个数组上进行操作，快指针去在这个数组上获取新的元素的值；慢指针在该数组上进行更新(只有在=val的时候才是有意义的覆盖操作)

虽然代码写起来很简单，但是整个操作细节还是很多，使用fast去循环，使用slow去return

实际上讲解思路后我自己去实现就会多出一些变量之间的拷贝，不会这么简洁优雅

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //实际上就是实现erase()函数的内部操作
        int fast=0,slow=0;
        for(fast=0;fast<nums.size();fast++){
            if(nums[fast]!=val){
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

保证了复杂度O(n)

时长：自己写10min

视频10min

重新手撕3min

977有序数组的平方

暴力

遍历+排序 O(nlogn)

双指针思想

妙哉妙哉，两边肯定是最大的，越往中间越小，虽然题目说是，从小到排序，但是我们可以先在vector里面开出nums那么大的空间，从末尾向前填写

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size(),0);
        int i=0;
        int j=nums.size()-1;
        int index = nums.size()-1;
        while(i<=j){
            if(nums[i]*nums[i]<nums[j]*nums[j]){
                res[index--] = nums[j]*nums[j];
                j--;
            }else{
                res[index--] = nums[i]*nums[i];
                i++;
            }
        }
        return res;
    }
    
};

时间复杂度：O(n)

时长：自己做3min

视频：5min

重新写：3min