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

704. 二分查找 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2: 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1 提示： 你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。、

思路： 因为是第二次刷题，这题还是有些简单的，一开始写的代码超时，分析原因主要是没有提前把target不在数组内的可能性用if语句删除掉。另一方面，对于预防mid越界，也需要注意一下。

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length-1]){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left+((right-left) >> 1);
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid +1;
            }else{
                right = mid -1;
            }
        }
        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。 你不需要考虑数组中超出新长度后面的元素。

思路： 1、暴力法 原地，我能想到的就是遍历该数组，然后只要出现数组中元素与给定的val一致，就将此元素后面的元素全部往前移一位，这样就会导致整体的数组长度减1，相当于用后面的元素覆盖该元素的位置。我一开始用的是一层for循环编写的程序，能过52个例子，但是卡在第53个实例过不去，一开始的想法就是，设定一个count用来记录重复的元素个数，如果发生重复，就让后一个数据移到前一个数据位置上，同时count加1。最后结果就是原数组长度减去count就是现有的数组长度，这种乍一看没问题，但错误的地方很明显，如果元素不重复，就顺利遍历，这时候会造成局部前移，而非整体前移。

看完卡哥的暴力法求解发现使用的两层for循环，这样只要出现重复元素，肯定是整体前移，不会造成局部的效果。出现重复元素，数组长度会减1，该元素i坐标，会因为后面j个元素前移，而减一。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        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;
    }
}

2、双指针法 思路： 双指针的思路还是不太好理解，看了卡哥的动画，不太能写的出来，还是看的代码才能写出来的。定义一个快指针fast，寻找新数组的元素，不含val的新数组；定义一个慢指针slow，指向更新新数组的下标位置。相当于fast指针遇到重复元素就跳过，非重复元素就赋值给slow。

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

总计1.5h