Sắp xếp màu (Sort Colors) trong Python

Giả sử chúng ta có một mảng với n đối tượng. Chúng được tô màu đỏ, trắng, hoặc xanh dương, sắp xếp chúng tại chỗ (in-place) sao cho các đối tượng cùng màu liền kề. Với thứ tự màu đỏ, trắng, xanh dương. Ở đây, chúng ta dùng số 0, 1, và 2 để đại diện cho màu đỏ, trắng, xanh dương tương ứng. Ví dụ, nếu mảng là [2,0,2,1,1,0], đầu ra sẽ là [0,0,1,1,2,2].

Để giải quyết, chúng ta làm theo các bước sau:

• Đặt low := 0, mid := 0 và high := độ dài mảng - 1.
• Khi mid <= high:
  • Nếu arr[mid] = 0, hoán đổi arr[mid] và arr[low], tăng low và mid lên 1.
  • Ngược lại khi arr[mid] = 2, hoán đổi arr[high] và arr[mid], giảm high đi 1.
  • Ngược lại tăng mid lên 1.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def sortColors(self, nums):
        low = 0
        mid = 0
        high = len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 2:
                nums[high], nums[mid] = nums[mid], nums[high]
                high -= 1
            else:
                mid += 1
        return nums

ob1 = Solution()
print(ob1.sortColors([2,0,2,1,1,0]))

Đầu vào

[2,0,2,1,1,0]

Đầu ra

[0,0,1,1,2,2]