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

2023-12-14 05:12:07

LeetCode 704 二分查找

题目链接:704.二分查找

本题思路:本题题目写的是二分查找,所以我们用到的算法肯定也是二分查找,需要定义 3个变量。
l: 从数组的下标0开始
r: 数组长度 - 1
mid:(l + r)>> 1,当数字很大的时候,会发生溢出,所以建议使用 l + ((r - l) >> 1)
所谓的二分查找就是每次找中间的那个值,判断是否与目标值相等,如果相等返回下标。如果不相等,再根据当前值和目标值大小,确定是 l++, 还是 r–。最终找到就返回下标,没找到就返回-1。

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length -1]){
            return -1;
        }
        int l = 0;
        int r = nums.length - 1;
        int mid = l + ((r - l) >> 1);
        while(l <= r){
            if(nums[mid] == target){
                return mid;
            }else if ( nums[mid] < target ){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            mid = l + ((r - l) >> 1);
        }
        return -1;
    }
}

下面用一个图,来演示下测试用例的一个过程,以便更加直观的分析了解代码。
在这里插入图片描述

  • 第一次判断的时候, nums[mid] != 9,并且 3<9,说明要找的目标值大于mid的值,所以目标值可能在 mid 的右边。在这里插入图片描述
  • 此时 l = mid + 1 = 3 ; mid = l + ((r-l)>>1) = 4。再判断 nums[mid] == 9。所以直接返回 mid 下标4在这里插入图片描述

注意事项:就是写代码的时候 while(left <= right) 还是 while(left < right)
上述代码使用的是 左闭右闭的一个区间:[0,nums.length-1],所以使用while(left <= right ),如果mid的值不等于target的话,那么要么就是 l = mid + 1,或者 r = mid - 1。

另一种写法为:左闭右开

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, 
        int r = nums.length;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                l = mid + 1;
            else if (nums[mid] > target)
                r = mid;
        }
        return -1;
    }
}

LeetCode 27 移除元素

题目链接:27.移除元素
本题思路:使用双指针思想,一个慢指针pre,一个快指针cur。初始都在 0位置,然后利用 快指针往后遍历,判断当前值是否等于 目标值,如果不等于,就存到 nums[pre]中,然后 pre++ , 如果等于就继续移动 cur,直到超出范围。

class Solution {
    public int removeElement(int[] nums, int val) {
        int pre = 0;
        int cur = 0;
        while( cur < nums.length){
            if(nums[cur] != val){
                nums[pre] = nums[cur];
                pre++;
                cur++;
            }else{
                cur++;
            }
        }
        return pre;
    }
}

下面用一个图,来演示下测试用例的一个过程,以便更加直观的分析了解代码。
在这里插入图片描述

  • 首先 pre = cur = 0, 先判断 nums[cur] 是否等于 val, 发现不等,所以让 nums[pre] = nums[cur],然后 cur++,pre++在这里插入图片描述
  • 再一次从上图开始判断 nums[cur] 是否等于 val,发现相等,所以直接 cur++,数组 nums[pre]不赋值。在这里插入图片描述
  • 此时上图还是 判断nums[cur] 是否等于 val,发现相等,所以直接 cur++,数组 nums[pre]不赋值。在这里插入图片描述
  • 最后发现 nums[cur] 不等于 val,所以让 nums[pre] = nums[cur],然后 cur++,pre++在这里插入图片描述
  • 到这里的时候循环 cur = nums.length,不满足循环条件退出循环。返回 pre的值为2。

文章来源:https://blog.csdn.net/hero_jy/article/details/134984310
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。