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

数组理论基础

文章链接：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;
    }
}