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

704.二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/
文档讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

思路

• 当区间定义为左闭右开时，right的初始值应该是nums.length，因为区间不包含这个值。left移动时，因为区间包含了left的值，而nums[middle]已经被比较过，所以left移动到middle + 1的位置。right移动时，因为区间没有包含right的位置，所以right应该移动到middle的位置。
• 当区间定义为左闭右闭时，right的初始值应该是nums.length - 1，因为区间包含这个值，如果是nums.length就没有意义。left移动同上，right移动时，因为区间包含了right的值，而nums[middle]已经被比较过，所以right移动到middle - 1的位置。

代码

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

分析：两种方法均为时间复杂度：O(logn)，空间复杂度：O(1)。

总结
之前零零散散刷过一些题，所以对二分法还有点记忆。虽然大概知道开闭的一些需要注意的点，但在实际做的时候还是错了好几次才通过。首先是在循环里没有写middle的赋值，很粗心。然后是忽略了right的初始赋值时开闭区间的问题，导致错误。

27.移除元素

题目链接：https://leetcode.cn/problems/remove-element/
文档讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP/

思路

• 暴搜是两层for循环，第一层遍历数组，遇到val相等的，再进入一层for循环把后面所有元素往前移。
• 快慢指针是快指针fast遍历数组，遇到和val不相等的数就放入慢指针slow，然后慢指针slow++。

代码

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

分析：
暴搜时间复杂度：O(n^2)，空间复杂度：O(1)。
快慢指针法时间复杂度：O(n)，空间复杂度：O(1)。

总结
移除元素做的还是比较顺的，就是我以为的暴搜其实好像只是另外一种双指针的写法。正常的暴搜应该是两层for循环，第一层遍历数组，遇到val相等的，再进入一层for循环把后面所有元素往前移。

本次目标
一刷代码随想录的时候刷到二叉树就开始懈怠，后面又零零散散做了一些动态规划和贪心算法，但是发现笔试的时候前面刷过的知识点完全运用不起来。希望这次能够坚持两个月，把基础打好，并且掌握二叉树。