【算法 day01】LeetCode 704二分查找 | 27移除元素 | 977有序数组的平方

704 二分查找

题目链接：二分查找

文档讲解：代码随想录文章讲解

视频讲解：代码随想录视频讲解

1.暴露破解解法：

 public int violentCracking(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==target){
                return i;
            }
        }
        return -1;
    }

时间复杂度:o(n)    空间复杂度:o(1)

2.左闭右闭解法：

2.1思路：

• [left,right],所以一开始left=0,right=nums.length-1,而不能是nums.length
• while循环，当left=right时，[left,right]是有效的区间，所以循环条件是left<=right
• 当中间节点值<target，左节点=middle+1 ,当中间节点>target， 右节点=middle-1 ,当中间节点=target，返回下标

2.2代码：

 public int search(int[] nums, int target) {
        int left=0;
        //右闭[left,right],所以right是一个被包含在内的值
        int right=nums.length-1;
        //right==left,[left,right]是有效的,所以用<=
        while (left <= right) {
            int middle=(left+right)/2;
            if(nums[middle]>target){
                //[left,right],middle是不符合条件的,所以[left,middle-1]
                right=middle-1;
            }
            if(nums[middle]<target){
                //[left,right],middle是不符合条件的,所以[middle+1,right]
                left=middle+1;
            }
            if(nums[middle]==target){
              return middle;
            }
        }
        return -1;
    }

时间复杂度:o(longn)  空间复杂度:o(1)

3.左闭右开解法：

3.1思路：

• [left,right),所以一开始left=0,right=nums.length,保证右区间的值是取不到的
• while循环，left==right时，[left,right)区间无效，所以循环条件是left<right
• 当中间节点值<target，左节点=middle+1 ,当中间节点>target， 右节点=middle ,当中间节点=target，返回下标

3.2代码：

public static int searchRightOpen(int[] nums, int target) {
       int left=0;
       //右开[left,right),不包含右区间,所以right=nums.length,但是并不会取到该值
       int right=nums.length;
       //右开,[left,right),所以left<right,不能包含=,例[1,1),这个区间无效
        while (left < right) {
            int middle = (left + right) / 2;
            if (nums[middle] > target) {
                //右开,[left,right),middle是不符和条件的，所以右区间是middle,若写成middle-1,那么就会漏判断
                right = middle;
            }
            if (nums[middle] < target) {
                //左闭,middle是不满足条件的，所以左区间是middle+1
                left = middle + 1;
            }
            if (nums[middle] == target) {
                return middle;
            }
        }
       return -1;
    }

时间复杂度:o(logn)  空间复杂度:o(1）

总结：二分法使用条件，数组是升序的，且没有重复元素，写代码的时候，要注意根据区间的定义来判断临界值

27 移除元素

题目链接：移除元素

文档讲解：代码随想录文章讲解

视频讲解：代码随想录视频讲解

1. 思路：

 移除数组中等于val的值，并返回数组中不等于val的值个数.

• 不新增数组，使用快慢指针，快指针用于是寻找满足新数组元素(for循环中fast变量),慢指针用于存放到新数组元素的下标
• 快指针找到满足条件的值，放入数组[slow++]中，相当与覆盖原数组中元素
• 慢指针slow的大小就是数组中不等于val的个数
• 注： 数组在[slow+1,nums.length-1]区间仍是有值的，值就是原来对应位置的值

2.代码：

public static 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];
                slow++;
            }
        }
        System.out.println(Arrays.toString(nums));
        return  slow;
    }

时间复杂度:o(n)  空间复杂度:o(1)

977 有序数组的平方

题目链接：有序数组平方

文档讲解：代码随想录文章讲解

视频讲解：代码随想录视频讲解

1.思路：

题意是将数组元素进行平方，升序排序后返回该数组。数组元素是递增的且存在负数，所以可知最大的元素在原数组的左右两边，考虑使用双指针

• 新建一个数组和一个指针A(初始值是新数组元素的长度，用于记录在新数组哪个位置放元素)
• 使用双指针，初始时分别指向数组第一个元素和最后一个元素
• 循环，判断左指针和右指针平方的大小，将较大的放入新数组中(倒序存放后指针A--)，对应的左指针（left++）或右指针(right--)移动，直到左右指针相遇，结束循环

2.代码：

 /**
     *  [-7,-3,2,3,11]
     * 0 4              121
     * 0 3           49 121
     * 1 3         9 49 121
     * 1 2       9 9 49 121
     * 2 2     4 9 9 49 121
     * @param nums
     * @return
     */

    public static int[] sortedSquares(int[] nums) {
        int left=0;
        int right=nums.length-1;
        int[] newNums=new int[nums.length];
        int i=newNums.length-1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                newNums[i] = nums[left] * nums[left];
                left++;
                i--;
            }else {
                newNums[i] = nums[right] * nums[right];
                right--;
                i--;
            }
        }
        return newNums;
    }

时间复杂度o(n)   空间复杂度o(n)