您现在的位置是:首页 >其他 >代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。网站首页其他

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

Matakgo 2023-05-28 16:00:02
简介代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。

704. 二分查找

题目链接:704. 二分查找
我的代码:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target > nums[middle]) left = middle + 1;
            else if (target < nums[middle]) right = middle -1;
            else return middle;
        }
        return -1;
    }
}
  1. 采用左闭右闭的方式:
    int right = nums.length - 1 和 while (left <= right) 的 “-1”和“<=”要注意。
  2. 注意循环语句,是while而不是for。

随想录代码:

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        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 (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}
  1. 补充了target有效判定
  2. int mid = left + ((right - left) >> 1) 防止溢出
    int middle = left + ((right - left) / 2)等同于(left + right)/2,但是left + right这个值会很大,可能超过实际的计算机内存。

27. 移除元素

题目链接:27. 移除元素
我的代码:

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left ++;
            }
            else {
                 // right++ 已经包含在循环条件内的了,除了右指针右移,其他不需要操作
            }
        }
        return left;
    }
}

双指针法——思路及算法
由于题目要求删除数组中等于 val 的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。可以使用双指针:右指针 right 指向当前将要处理的元素,左指针 left 指向下一个将要赋值的位置。

  • 如果右指针指向的元素不等于 val ,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移;
  • 如果右指针指向的元素等于 val ,它不能在输出数组里,此时左指针不动,右指针右移一位。
    整个过程保持不变的性质是:区间 [0, left ) 中的元素都不等于 val 。当左右指针遍历完输入数组以后, left 的值就是输出数组的长度。即,左指针指向的为新的输出数组(在原数组中的输出数组),返回left就是移除后数组的新长度。
    这样的算法在最坏情况下(输入数组中没有元素等于 val ),左右指针各遍历了数组一次。

与随想录代码一样

  1. else语句里没有内容。上层循环默认right是++的,所以不需要else里再操作。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。