代碼隨想錄算法訓(xùn)練營第一天| 704. 二分查找, 27.移除元素, 977.有序數(shù)組的平方

學(xué)習(xí):https://blog.csdn.net/weixin_53740387/article/details/127000994

704.二分查找

特點(diǎn) : 有序數(shù)組,無重復(fù)元素

思路:通過將target與查找范圍數(shù)組的中間值作比較來縮小查找范圍(先判定target大小是否在數(shù)組范圍內(nèi))

掌握方法 : 左閉右閉 左閉右開(重點(diǎn):while的條件是否為合法區(qū)間; right變化是否包含middle)

• 左閉右閉:while的條件合法區(qū)間 left <= right ; right變化包含 middle

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //防止target大小不在數(shù)組范圍內(nèi)影響效率
        if(target < nums[0] || target > nums[right]){
            return -1;
        }
        while(left <= right){
            int middle = (left + right) / 2;
            if(nums[middle] < target){
                left = middle + 1;
            }
            else if(nums[middle] > target){
                right = middle - 1;
            }
            else{
                return middle;
            }
        }
        return -1;
    }
}

• 左閉右開:while的條件合法區(qū)間 left < right ; right變化不包含 middle

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        //防止target大小不在數(shù)組范圍內(nèi)影響效率
        if(target < nums[0] || target > nums[right - 1]){
            return -1;
        }
        while(left < right){
            int middle = (left + right) / 2;
            if(nums[middle] < target){
                left = middle + 1;
            }
            else if(nums[middle] > target){
                right = middle;
            }
            else{
                return middle;
            }
        }
        return -1;
    }
}

27.移除元素

• 暴力拆解??(n方)

我的問題: 1. for中 i 和 j 判定條件 : 我寫的 nums.length 和 nums.length - 1

? 2. 沒有在 if 后 i-- 操作

錯(cuò)誤原因: 1. 我沒有考慮到數(shù)組內(nèi)元素前移后,后面的臟數(shù)據(jù)會(huì)影響我的結(jié)果,且后面的臟數(shù)據(jù)可以不管

? 2. 沒有考慮如果有兩個(gè)符合val值的數(shù)挨在一起,向前覆蓋,此時(shí)我的i++,已經(jīng)移到了后面,會(huì)出現(xiàn)錯(cuò)誤

? 如 :

class Solution {
    public int removeElement(int[] nums, int val) {
        //暴力拆解
        int n = nums.length;
        for(int i = 0; i < n; i++){
            if(nums[i] == val){
                for(int j = i; j < n - 1; j++){
                    nums[j] = nums[j + 1];
                }
                i--;
                n--;
            }
        }
        return n;
    }
}

• 雙指針法:O(n)

? 快指針負(fù)責(zé)尋找符合結(jié)果的值, 慢指針符合從0開始填入符合結(jié)果的值(因?yàn)閿?shù)組中的值不能刪除,只能覆蓋)

class Solution {
    public 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];
        }
      }
      return slow;
    }
}

977.有序數(shù)組的平方

與上一道雙指針的共同點(diǎn), 尋找符合要求的數(shù)組內(nèi)容放在新數(shù)組中(這個(gè)新數(shù)組也可能是在原來的數(shù)組上操作)

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