代码随想录刷题记录第一天 | 数组 | 704. 二分查找，27. 移除元素

虚拟式 / 2024-03-21 / 原文

题目链接:
704. 二分查找 - https://leetcode.cn/problems/binary-search/description/
27. 移除元素 - https://leetcode.cn/problems/remove-element/description/

文章学习链接：https://programmercarl.com/数组理论基础.html
视频学习链接：https://www.bilibili.com/video/BV1fA4y1o715

704. 二分查找

题目内容:给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路：由题意的，是二分查找，所以直接使用了二分查找的方法。

二分查找

使用条件

用于查找的内容逻辑上来说是需要有序的
查找的数量只能是一个，而不是多个（多个返回结果可能不一样）

步骤：
确定一个左边界，一个右边界，判断要求的值是否在范围内，如果不在，是大于目标值还是小于目标值，然后以此调节范围

解答代码

class Solution {
     public int search(int[] nums, int target) {
        // 判断数组非空 和 简单的范围判断（因为有序）
        if(nums == null || target > nums[nums.length -1] || target < nums[0]){
            return -1;
        }
        // 给定初值边界
        int left = 0;
        int right = nums.length;
        int mid ;
        // 当左边大于等于右边,跳出循环
        while(left < right){ 
            mid = (right + left)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] > target){  // target 在左区间，在[left, middle)中
                right = mid;
                continue;
            }
            if(nums[mid] < target){ // target 在右区间，在[middle + 1, right)中
                left = mid +1 ;
                continue;
            }
        }
        return -1;
    }
}

出现的问题：
一开始超出时间限制了 >.<

注意点：
1、mid = (right + left)/2 是加，不是减，是求两个点之间的中值
2、left = mid + 1 那里和 right = mid 区别

二分法有两种写法
一种取值是left、right是闭区间的，即left和right都在数组内，[left，right]
一种取值是left、right是左闭右开，即[left,right)

当选择第二种时注意，让right一直处于开区间的那，（由第二个注意点那里保证）。

27. 移除元素

题目内容:给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路：暴力破解，双指针法

1、暴力破解

步骤：逐个匹配，当匹配到和给定的val值一样的时候，将后面的元素都往前提一个元素。两层for循环，一个for循环遍历数组元素，第二个for循环更新数组。

代码:

class Solution {
    public int removeElement(int[] nums, int val) {
        int target = 0; //记录val值的个数
        int len = nums.length; // 原数组长度
        for(int i = 0 ; i< len;i++){ //i<len 最大可到 len - 1 （原数组最大下标）
            if(nums[i] == val){ //等于则将后面的元素都往前移
                for(int j = i; j< len - 1; j++){ // j<len-1 最大可到 len - 2 ，防止j+1下标越界，当进入到这里面的时候也只少会有一个val 
                    nums[j] = nums[j+1]; 
                }
                target++; 
                i--; // 为了判断前移的第一个元素是否等于val 
            }
            if(i == len - target - 1){ // 当长度到len - target - 1 就不用判断了
                break;
            }
        }
        return len - target;
    }
}

注意点
1、匹配时候同时出现两个val值连在一起时
2、给定的数组只有一个元素或是没有元素的时候

2、双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

步骤：
定义快慢指针
快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

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

或者相向，（题目提示说可以无序）