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

发布时间:2024年01月11日

数组理论基础

文章链接:https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

704.二分查找

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

(1)第一种写法:左闭右闭。

因为是根据区间的定义,确定循环中的变量的取值。

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 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;
        int middle;
        // int middle = (left+right)/2;
        int result = -1;
        while(left <= right){
            middle = (left+right) >> 1;
             if(nums[middle]>target){
                 right = middle - 1;
             }else if (nums[middle] < target){
                 left = middle + 1;
             }else
                return middle;
        }
        return -1;
    }
   
}

(2)第二种写法:左闭右开

有如下两点:

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]
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;
        int middle;
        // int middle = (left+right)/2;
        // int result = -1;
        while(left < right){
            middle = (left+right) >> 1;
             if(nums[middle]>target){
                 right = middle;
             }else if (nums[middle] < target){
                 left = middle + 1;
             }else
                return middle;
        }
        return -1;
    }
   
}

27.移除元素

题目连接:https://leetcode.cn/problems/remove-element/description/

暴力解法:

时间复杂度(O^2)

两层for循环,第一个for循环遍历数组元素,第二个for循环更新数组

class Solution {
    public int removeElement(int[] nums, int val) {
        
        int x = nums.length;
        for(int i = 0; i < x;i++){
            if(nums[i] == val){
                for(int j=i+1;j<x;j++){
                    nums[j-1] = nums[j]; 
                }
                i--;
                x--;
            }

        }
        return x;
    }
}

双指针法:

时间复杂度O(n)

定义一个慢指针,一个快指针,要明确的是这里快指针和慢指针有什么不同。

慢指针,指向的是新数组下标的位置。

快指针,指向的是不含有目标元素的数组,跳过值一致的元素

class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex< nums.length;fastIndex++){
            if(nums[fastIndex] != val){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
}
文章来源:https://blog.csdn.net/Captain_Aaron/article/details/135534268
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。