當前位置：首頁 > 运维知识 > windows >内容正文

windows

经典数据结构题目-数组

發布時間：2024/1/16 windows 28 coder

生活随笔收集整理的這篇文章主要介紹了经典数据结构题目-数组小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

704. 二分查找

解決思路
- 基于數組有序的特性，取其中一個值進行比較，即可淘汰該值左邊或右邊的元素，縮小搜索的區間
- 使用兩指針標記需要遍歷的區間，取中間值進行比較，淘汰左邊或右邊元素，不斷移動縮小遍歷的區間，即可查到

代碼

public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){  // 注意點一
            int mid = l + (r-l)/2;
            if(nums[mid] > target){
                r = mid - 1; // 注意點二
            }else if(nums[mid] < target){
                l = mid + 1;
            }else{
                return mid;
            }
        }
        return -1; 
    }

注意點
- 核心注意點：避免漏檢元素
- 注意點一：while條件中選擇 l <= r 還是 l < r ，取決于 r 的取值；當 r = num.length時，l 不能 <= r，可能會溢出
- 注意點二：當選擇 l < r 的判斷時，while中每次搜索的區間為 [l,r) 。當num[mid] > target時，r = mid，不能mid-1。因為r所指向的元素在進入第二次循環時，是不會再與target比較，會導致漏檢
- 時間復雜度 O(logN) 。總共需要遍歷 log2N次，忽略常數2。

擴展

當元素可重復時，如何定位到與target相等的最小索引

public static int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] >= target){
                // 等于target的時候 右指針繼續移動，繼續尋找最左邊的一個
                // 如果已達最左的一個，再循環左指針會移動，最終會大于r，取到最左的
                r = mid - 1;
            }else if(nums[mid] < target){
                l = mid + 1;
            }
        }
        // 會存在找不到與target相等的情況
        if(nums.length == l || nums[l] != target){
            return -1;
        }
        return l;
    }

80. 刪除有序數組中的重復項 II

解決思路
- 使用快慢指針遍歷，快指針用于判斷是否與上一個元素重復，慢指針用于記錄下最終有效的數字
- 快指針判斷為不重復，慢指針記下來，同時向前移動一位

代碼

    public int removeDuplicates(int[] nums) {
        // 只允許元素出現一次的情況
        int k = 1;
        int fast = k;
        int slow = k; // 注意點一
        while(fast < nums.length){
            if(nums[fast] != nums[fast-k]){ // 注意點二
                nums[slow] = nums[fast];
                slow++;
            }
            fast ++;
        }
        return slow;
    }

注意點
- 核心注意點：理清快慢指針分別的作用
- 注意點一：快慢指針的起始位置，k <= nums.length時，可以初始化快慢指針在k的位置開始遍歷
- 注意點二：判斷元素是否超過k個重復，因為數組有序，如果當前元素等于前k個位置的元素，說明超過了
同類型題目
- https://leetcode.cn/problems/remove-element/description/
- https://leetcode.cn/problems/move-zeroes/description/

977. 有序數組的平方

解決思路
- 非遞減順序。即遞增但可以重復
- 使用雙向指針，比較兩指針指向元素的絕對值，絕對值大的計算平方添加進結果數組

代碼

 public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int l = 0;
        int r = nums.length-1;
        int index = nums.length - 1;
        while(l <= r){
            if(Math.abs(nums[l]) > Math.abs(nums[r])){
                res[index] = (int)Math.pow(nums[l],2);
                l++;
            }else{
                res[index] = (int)Math.pow(nums[r],2);
                r--;
            }
            index --;
        }
        return res;
    }

注意點
- 這里空間復雜度為O(1)，不是O(n)，因為空間復雜度是計算非答案占用的空間

擴展

想再節省空間的話，可以比較兩個數的平方后，進行交換，右指針一直往前移即可

public int[] SortedSquares(int[] nums) {
    int left = 0;
    int right = nums.length-1;
    int leftR = 0, rightR = 0;
    while(right >= 0){
      leftR = nums[left]*nums[left];
      rightR = nums[right]*nums[right];
      // 左指針的平方比較大，交換到數組的后面來
      if(leftR >= rightR){
        nums[left] = nums[right];
        nums[right] = leftR;
      }else{
        nums[right] = rightR;
      }
      right--;
    }
    return nums;
}

總結

以上是生活随笔為你收集整理的经典数据结构题目-数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。