当前位置：首页 > article >正文

代码随想录算法训练营第1天（数组1）| 704. 二分查找、27. 移除元素、977.有序数组的平方

article 2025/1/9 14:31:11

一、704 二分查找

题目：https://leetcode.cn/problems/binary-search/

视频：https://www.bilibili.com/video/BV1fA4y1o715

讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

二分查找前提：有序，无重复

二分法区间有两种：左闭右闭 [left, right]，左闭右开 [left, right)

这个题的关键是：边界的处理

三个变量：left, right,middle

需要注意：

1、while(left< or <= right)—>看是否合法

左闭右闭(<=) or 左闭右开(<)，这两种方式怎么取值，主要取决于区间是否成立(把=单拎出来看情况是否合法)

[left, right] [3,3] 合法

[left, right） [3,3）不合法

2、if（nums[mid] > target) right=mid or right=mid-1 ---->看是否比较过

解法一：左闭右闭

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length-1]) return -1;

        int left = 0, right = nums.length-1;

        while(left <= right){
            int mid = left + ((right - left)>>1);   //
            if (target == nums[mid]) {
                return mid;
            } else if(target < nums[mid]){
                right = mid - 1;
            }else{
                left = mid +1;
            }
        }
        return -1;
    }
}

位运算

(right - left) >> 1：将当前搜索区间的长度除以2，得到中间位置距离left索引的距离。这里使用的是位运算符>>，它表示无符号右移1位，相当于除以2。使用位运算符可以提高计算效率。

left + ((right - left) >> 1)：将left索引与中间位置距离相加，得到中间位置的索引值，即mid。

总结优先级顺序（从高到低）：

乘法（*）和除法（/）
左移（<<）和右移（>>）
与（&）和异或（^）
加法（+）和减法（-）
或（|）

使用括号（<font style="color:rgb(6, 6, 7);">()</font>）可以改变运算的优先级，使得括号内的运算优先执行。

尝试记录:

第 1 次：

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return -1;    //1

        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right)/2;    //2

        while(left <= right){
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            } 
        }
        return -1;
    }
}

结果：超时

问题：

1、开始的判空没必要，应该改成是： target 和有序数组首尾元素的判断，即比最小的小、比最大的大就不用判断了。

2、mid 写错位置，每次都有变化，应该写在循环里

第二次：

class Solution {
    public int search(int[] nums, int target) {
        // if(nums == null || nums.length == 0) return -1;
        if(target > nums[nums.length-1] || target < nums[0]) return -1;

        int left = 0;
        int right = nums.length - 1;
        

        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            } 
        }
        return -1;
    }
}

改进

加入位运算

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length-1]) return -1;

        int left = 0, right = nums.length-1;

        while(left <= right){
            int mid = left + ((right - left)>>1);
            if (target == nums[mid]) {
                return mid;
            } else if(target < nums[mid]){
                right = mid - 1;
            }else{
                left = mid +1;
            }
        }
        return -1;
    }
}

解法二：左闭右开

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length-1]) return -1;

        int left = 0, right = nums.length-1;

        while(left < right){        //
            int mid = left + ((right - left)>>1);
            if (target == nums[mid]) {
                return mid;
            } else if(target < nums[mid]){
                right = mid;
            }else{
                left = mid +1;    //
            }
        }
        return -1;
    }
}

二、27 移除元素

题目：https://leetcode.cn/problems/remove-element/

视频：https://www.bilibili.com/video/BV12A4y1Z7LP

讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

双指针思想（一层 for 循环解决）

快指针+慢指针

快指针所指向的数组元素如果不等于 val -》把快指针指向的值赋给慢指针指向的值，之后慢指针往后一位

快指针所指向的数组元素等于 val-》不走 if，fast 直接后移

快指针带动慢指针走：快指针动了，把值赋给慢指针，慢指针后移

在原数组上修改（覆盖）

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];
            }
        }
        return slow;      
    }
}

三、977.有序数组的平方

题目：https://leetcode.cn/problems/squares-of-a-sorted-array/

视频：https://www.bilibili.com/video/BV1QB4y1D7ep

讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

双指针

慢指针在左边界，快指针在右边界，平方放到新数组中

慢指针对应元素的平方大-》慢指针平方放到新数组中，慢指针后移

快指针对应元素的平方大-》快指针平方放到新数组中，快指针前移

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int k = result.length-1;

        for(int fast=nums.length-1, slow=0; fast>=slow; ){
            if(nums[slow]*nums[slow]>nums[fast]*nums[fast]){
                result[k--] = nums[slow]*nums[slow];
                slow++;
            }else {
                result[k--] = nums[fast]*nums[fast];
                fast--;
            }
        }
        return result;
    }
}