荷蘭國旗問題LeetCode：如何解決

什麼是荷蘭國旗問題LeetCode？

荷蘭國旗問題是一道在LeetCode上經常出現的編程問題。這個問題要求根據給定的數組，將數組中的元素按照紅、白、藍的順序進行排序。具體的問題描述和解決方法如下：

問題描述

給定一個只包含 0、1、2 三種元素的整數數組 nums，原地對它進行排序，使得相同顏色的元素相鄰，按照紅、白、藍的順序排列。這裡，我們使用整數 0、1 和 2 分別表示紅色、白色和藍色。

注意：

• 不能使用代碼庫中的排序函數來解決這道題。
• 排序后的數組必須滿足原始問題中要求的順序。
• 題目中要求使用原地演算法進行排序，不能創建一個新的數組。

解決方法

解決荷蘭國旗問題的一種常用方法是使用三個指針，分別指向數組的左邊界、當前位置和右邊界。遍曆數組，根據當前元素的值，將元素放置在正確的位置上。

具體步驟如下：

1. 初始化三個指針：left = 0，right = n - 1，curr = 0。
2. 遍曆數組，循環結束條件是 curr <= right。
3. 如果 nums[curr] == 0，則將元素與左邊界的元素交換，並將 left 和 curr 的值加 1。
4. 如果 nums[curr] == 1，則將 curr 的值加 1。
5. 如果 nums[curr] == 2，則將元素與右邊界的元素交換，並將 right 的值減 1。

示例代碼

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int curr = 0;
        
        while (curr <= right) {
            if (nums[curr] == 0) {
                int temp = nums[left];
                nums[left] = nums[curr];
                nums[curr] = temp;
                left  ;
                curr  ;
            } else if (nums[curr] == 1) {
                curr  ;
            } else {
                int temp = nums[right];
                nums[right] = nums[curr];
                nums[curr] = temp;
                right--;
            }
        }
    }
}

總結

荷蘭國旗問題是一道常見的編程問題，通過使用三個指針來解決，可以很好地對數組進行排序。這種方法的時間複雜度為 O(n)，非常高效。掌握了解決荷蘭國旗問題的方法，可以幫助我們更好地理解和解決其他類似的排序問題。