Eisen 筆記

#75. Sort Colors

題目描述

給你一個陣列nums含有紅色、白色和藍色的物件n，直接在給定的陣列中進行整理，讓同一個顏色的物件相鄰，並且以紅、白、藍的順序排列。

我們使用整數0、1、2來表示紅色、白色和藍色。

你不能使用基本函式庫中的Sort函式來解決問題。

限制條件

  1. n == nums.length
  2. 1 <= n <= 300
  3. nums[i]只會是0、1和2。

解題思路

Pointers

這一題首先我們先設立兩個指針，一個是負責定位0的終點zeroIdx，另一個是負責定位2的起點twoIdx，舉例來說：

nums = [0,0,0,1,1,1,2,2,2]

這個時候的zeroIdx = 4，twoIdx = 6。 這兩個定位點代表了如果我們要排序0或2，要替換的位置。

以這個例子來說，
nums = [0,2,1,0,2]
這個時候的zeroIdx = 1，twoIdx = 3。 接下來當我們從頭開始檢查的時候，第一個會遇到的是2，之後我們將2換到twoIdx的位置上就會變成：
nums = [0,0,1,2,2]
直到我們碰到twoIdx時，就可以結束迴圈，因為twoIdx確保了它之後的位置都是2，我們不用多做處理。

public class Solution {
    public void SortColors(int[] nums) {        
        int zeroIdx = 0;
        int twoIdx = nums.Length-1;
        for(int i=0;i<nums.Length;i++){            
            if(i>twoIdx) break;            
            while(nums[zeroIdx]==0 && zeroIdx<twoIdx) zeroIdx++;
            while(nums[twoIdx]==2 && zeroIdx<twoIdx) twoIdx--;            
            if(nums[i]==2 && i<twoIdx){
                nums[i] = nums[twoIdx];
                nums[twoIdx] = 2;
                if(nums[i]==0 && i>0) i--;                
            }else if(nums[i]==0 && i>zeroIdx){
                nums[i] = nums[zeroIdx];
                nums[zeroIdx] = 0; 
            } 
        }        
    }
}

複雜度分析：

  • 時間複雜度：最差的情況下，zeroIdx會跑到最後一個元素，而for迴圈也要跑到最後一個元素才能處理完所有陣列，總時間會是2*n，時間複雜度為O(n)。
  • 空間複雜度：題目要求是In-place，因此空間複雜度為O(1)。

Follow-up

你可以使用單遍演算法來解決這個問題，並且只使用常數大小的空間嗎？

Solution

上面的解決策略就已經是滿足Follow-up的要求了。

學習重點

  • TwoPointers
  • Sort
Last Updated:
Contributors: eisen