LeetCode #75 Sort Colors 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

中文翻譯

給予一個陣列nums，包含n個物件以紅色、白色及藍色標記，排序他們(使用原地演算法 ➔ 可理解為不改變資料結構)，使相同顏色的物件能夠鄰近一塊(排序: 紅色、白色、藍色)

使用整數 0、1、2 來分別表示紅色、白色、藍色

你必須在不使用函式庫的排序函式解決問題

第一點題目第一句就提到了，陣列長度為n

n的長度介於1到300之間 ➔ 不用擔心無資料等例外狀況

陣列中僅有 0、1、2 ➔ 三個數字分別對應三種不同顏色

接下來是官方範例

這題其實比較單純，看到限制不能使用已有的排序函式，再看到範例，很容易就可以知道又做的就是根據 0、1、2排序

解題思路

氣泡排序法 Bubble Sort

講到排序，筆者第一個想到就會是「氣泡排序法」，最常見的排序演算法

主要核心原理為按順序兩兩數字比較，前者比後者大就交換，因為數字較小/大的會逐漸浮到最前/後，像氣泡浮出水面一樣，故因此得名

更詳細的可以參考 : 維基百科-泡沫排序、IThome鐵人賽有篇也寫得很好，這篇就不另詳細說明

C# 解決方案

方案1 – 氣泡排序法

public class Solution {
    public void SortColors(int[] nums) {
        
        int n = nums.Length;
        while(n>1)    //註1
        {
            n--;
            for(int i =0;i<nums.Length-1;i++)
            {
               if(nums[i] > nums[i+1]) 
               {
                   int tmp = nums[i];     //暫存int，為了兩個數字交換
                   nums[i] = nums[i+1];
                   nums[i+1] = tmp;
               }
            }
        }
    }
}

沒錯，就是這麼簡單，沒幾行

我們來看一下註1的部分，為什麼要n>1呢，其實這樣就會跑n-1次

假設現在有一數列 [4、3、2、1] ➔ 可以看到是最糟糕的狀況吧(以從index 0 做氣泡排序來看)

那每次運行結果會跟下面一樣(這裡的n 以及i 為上方範例程式的變數名稱)

時間複雜度 : O(n²)

註2 ➔ 可以看到 i =3 的狀況時 ，我們來判斷這個 nums[i] > nums[i+1]

目前的數字為 2134， nums[2] = 3 、nums[3] = 4，已排列完故不用交換 ➔ 3>4 = false

註3、註4則是同理

氣泡排序法的缺點也較為明顯，像是上面舉的那個例子，只有4個數字大家可能沒有感覺

可是4個數字就需要跑 (n-1)*(n-1)次 = 3*3 = 9次 (註2、註3、註4 其實都有跑到，只是不用交換而已)

時間複雜度方面，除非加入每次執行確認的程序，最好可為O(n) ➔ 完全不用交換，或只要交換n次

方案2 – 沒那麼短但相對好理解

public class Solution {
    public void SortColors(int[] nums) {
        int a = 0;
        int b = 0;
        int c = 0;
        
        //1.遞迴並計算
        foreach(int num in nums)
        {
            switch(num)
            {
                case 0:
                    a+=1;
                    break;
                case 1:
                    b+=1;
                    break;
                case 2:
                    c+=1;
                    break;
            }
        }
        
        //2.重寫Array
        int cnt = 0;
        while(a>0)
        {
            nums[cnt] = 0;
            a--;
            cnt++; 
        }
        
        while(b>0)
        {
            nums[cnt] = 1;
            b--;
            cnt++; 
        }
        
        while(c>0)
        {
            nums[cnt] = 2;
            c--;
            cnt++; 
        }
        
    }
}

時間複雜度 : O(n) ➡ 雖然用了很多個迴圈，但也只會跑到 2n次

差不多3,4個月後回來整理文章時想到，既然只有3種顏色 (0,1,2)

那我直接用3個 int 變數存不就好了嗎

Java解決方案

方案1 – 氣泡排序法

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        while(n>1)    
        {
            n--;
            for(int i =0;i<nums.length-1;i++)
            {
               if(nums[i] > nums[i+1]) 
               {
                   int tmp = nums[i];  
                   nums[i] = nums[i+1];
                   nums[i+1] = tmp;
               }
            }
        } 
    }
}

時間複雜度 : O(n²)

運行時間 : 12ms、4ms、4ms

⭐方案2

class Solution {
    public void sortColors(int[] nums) {
        int a = 0;
        int b = 0;
        int c = 0;
        
        //1.遞迴並計算
        for(int num : nums)
        {
            switch(num)
            {
                case 0:
                    a+=1;
                    break;
                case 1:
                    b+=1;
                    break;
                case 2:
                    c+=1;
                    break;
            }
        }
        
        //2.重寫Array
        int cnt = 0;
        while(a>0)
        {
            nums[cnt] = 0;
            a--;
            cnt++; 
        }
        
        while(b>0)
        {
            nums[cnt] = 1;
            b--;
            cnt++; 
        }
        
        while(c>0)
        {
            nums[cnt] = 2;
            c--;
            cnt++; 
        }
    }
}

時間複雜度 : O(n)

運行時間 : 0ms、0ms、0ms

Python3 解決方案

方案1

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        while(n>1):
            n-=1
            
            for i in range(len(nums)-1):
               if(nums[i] > nums[i+1]):
               
                   tmp = nums[i]
                   nums[i] = nums[i+1]
                   nums[i+1] = tmp

方案2

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        a = 0
        b = 0
        c = 0
        
        for num in nums:
            if num == 0:
                a+=1
            elif num == 1:
                b+=1
            else:
                c+=1
      
        cnt = 0
        while(a>0):
            nums[cnt] = 0
            a-=1
            cnt+=1
        
        while(b>0):
            nums[cnt] = 1
            b-=1
            cnt+=1
        
        while(c>0):
            nums[cnt] = 2
            c-=1
            cnt+=1

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var n = nums.length;
    while(n>1)    
    {
        n--;
        
        for (let i=0; i<nums.length-1; i++) {
            if(nums[i] > nums[i+1]) 
            {
                let tmp = nums[i];  
                nums[i] = nums[i+1];
                nums[i+1] = tmp;
            }
        }
    }
};

方案2

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var a = 0;
    var b = 0;
    var c = 0;
    
    nums.forEach(function(num){
        switch(num)
        {
            case 0:
                a+=1;
                break;
            case 1:
                b+=1;
                break;
            case 2:
                c+=1;
                break;
        }
    });
    
    var cnt = 0;
    while(a>0)
    {
        nums[cnt] = 0;
        a--;
        cnt++; 
    }

    while(b>0)
    {
        nums[cnt] = 1;
        b--;
        cnt++; 
    }

    while(c>0)
    {
        nums[cnt] = 2;
        c--;
        cnt++; 
    }
};

結論

這題考的是很基本的排序演算法，算是個入門容易、優化學問深如海的概念

不過現在Library 其實已經很發達了，大多時候是不用自己土法煉鋼，主要還是培養一個邏輯概念了

"It's kind of fun to do the impossible."
                                                                                                                 Walt Disney                            

題目連結 : Sort Colors – LeetCode

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡幫我點一個廣告，可以讓我月底不用煩惱主機錢 (┐「﹃ﾟ｡)

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

最新文章

• LeetCode #2073 Time Needed to Buy Tickets 買到票所需要的時間
• Java 比較字串或字元是否相等(忽略大小寫)
• C# 比較字串或字元是否相等(忽略大小寫)
• LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量
• LeetCode #1544 Make The String Great 讓字串變好