程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Sort Colors

LeetCode Sort Colors

編輯:關於C++

LeetCode解題之Sort Colors


原題

給出一個由紅、白、藍三種顏色組成的數組,把相同顏色的元素放到一起,並整體按照紅、白、藍的順序。用0表示紅色,1表示白色,2表示藍色。這題也稱為荷蘭國旗問題。

注意點:

盡量只遍歷一次

例子:

輸入: nums = [1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 0, 2]

輸出: [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2]

解題思路

如果只有兩種顏色,那麼很容易想到一前一後兩個指針向中間遍歷,顏色不對就交換位置。三種顏色仍然可以這麼做,只不過要多一個指針,前後兩個指針用來分隔已經排好的紅色和藍色,中間的指針來遍歷元素:

如果是紅色,那麼和前指針交換,並兩個一起向後移,前指針換過來的一定是白色的,因為中指針已經掃描過那些元素了 如果是白色,那麼繼續向後移 如果是藍色,那麼和後指針交換,後指針向前移,中指針不能後移,因為此時不確定換過來的元素是什麼顏色

AC源碼

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left = mid = 0
        right = len(nums) - 1
        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                left += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1


if __name__ == "__main__":
    l = [1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 0, 2]
    Solution().sortColors(l)
    assert l == [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2]
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved