LeetCode704 二分查找、LeetCode27 移除元素、LeetCode977 有序數組的平方

代碼隨想錄算法訓練營第一天 | 704-二分查找、27-移除元素、977-有序數組的平方

LeetCode704 二分查找

fA4y1o715

第一遍 自己獨立完成

一上來先自己做一遍，初看題目，分了三種情況畫圖：nums[mid] < target、nums[mid] > target、nums[mid] = target，再在外面套個while循環，自信滿滿點了提交hh，然後報錯：

代碼隨想錄算法訓練營第一天 704. 二分查找、27. 移除元素_數組

看了錯誤詳情，恍然大悟，發現我的while循環條件有誤：

如果循環判斷條件只是left<right的話，遇到‘’nums={5},target=5‘’的情況就不會進入循環，mid都求不到就返回-1了，這顯然不對

把這個條件改成left<=right，再遇到上述情況，就能夠成功進入循環，改變result，返回正確結果了：

代碼隨想錄算法訓練營第一天 704. 二分查找、27. 移除元素_i++_02

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;

        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                result = mid;
                break;
            }
        }

        return result;
    }
}

第二遍 看講解、深入刨析、做小結

二分法，把握好區間邊界問題，分清楚題目區間到底是左閉右閉還是左閉右開

左閉右閉[left, right]

  • 初始賦值 left = 0，right = nums.length - 1
  • [1,1]是合法區間，所以while(left <= right)
  • 當nums[mid] != target時，mid對應下標應排除出搜索區間，相應left = mid+1，right = mid-1

左閉右開[left, right)

  • 初始賦值 left = 0，right = nums.length
  • [1,1)是非法區間，所以while(left < right)
  • 當nums[mid] != target時，mid對應下標應排除出搜索區間，相應left = mid+1，right = mid

LeetCode27 移除元素

題目鏈接：https://leetcode.cn/problems/remove-element/

文章講解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

視頻講解：https://www.bilibili.com/video/BV12A4y1Z7LP

第一遍 自己獨立完成

初看題目，思路還算比較清晰：首先先建立一個nums2數組用於存放nums數組中不等於val的元素，再用k來計數。

第一次for循環，得到nums2數組和k的值

第二次for循環，再將nums2數組覆蓋到nums數組上，這樣nums數組前k個元素就能符合題目要求

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        int length = nums.length;
        int[] nums2 = new int[length];
        for(int i = 0;i < length;i++){
            if(nums[i] != val){
                nums2[k] = nums[i];
                k++;
            }
        }
        
        for(int i = 0;i < k;i++){
            nums[i] = nums2[i];
        }
        
        return k;
    }
}

第二遍 看講解、深入刨析、做小結

看了講解之後，發現還能使用雙指針的思路解這道題目

快指針用來獲取新數組中的元素，慢指針用來獲取新數組中需要更新的位置

因為slow從0開始，所以它最後指向的下標，就是新數組中元素的個數

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        int fast = 0;
        for(;fast < nums.length;fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        
        return slow;
    }
}

LeetCode977 有序數組的平方

題目鏈接：https://leetcode.cn/problems/squares-of-a-sorted-array/

文章講解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

視頻講解： https://www.bilibili.com/video/BV1QB4y1D7ep

第一遍 自己獨立完成

第一眼看到題目，首先想到的思路是先用一次for循環把nums數組所有元素平方，然後再用排序算法升序排序

這裏挑了比較好實現的冒泡排序，雖然題目AC，但很顯然，這代碼並不優雅，還有很多可改進的空間

代碼隨想錄算法訓練營第一天 704. 二分查找、27. 移除元素_數組_03

class Solution {
    public int[] sortedSquares(int[] nums) {
        int length = nums.length;
        for(int i = 0;i < length;i++){
            nums[i] = nums[i]*nums[i];
        }

        for(int i = 0;i < length;i++){
            for(int j = 0;j < length-i-1;j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }

        return nums;
    }
}

第二遍 看講解、深入刨析、做小結

看了講解以後，發現這題還能用雙指針的思路求解，時間複雜度來到O(n)

一左一右兩個指針逐漸向中間靠攏，由大到小生成一個新數組

最後用雙指針的思路寫了一遍，代碼十分優雅呀hh：

代碼隨想錄算法訓練營第一天 704. 二分查找、27. 移除元素_i++_04

class Solution {
    public int[] sortedSquares(int[] nums) {
        int length = nums.length;
        for(int i = 0;i < length;i++){
            nums[i] = nums[i] * nums[i];
        }

        int left = 0;
        int right = length - 1;
        int[] result = new int[length];
        int cnt = length - 1;
        while(left <= right){
            if(nums[left] <= nums[right]){
                result[cnt] = nums[right];
                cnt--;
                right--;
            }else{
                result[cnt] = nums[left];
                cnt--;
                left++;
            }
        }

        return result;
    }
}