Chương trình phân vùng danh sách màu trong Python

Cho danh sách chuỗi màu chứa "red", "green", "blue". Phân vùng sao cho "red" trước, "green" giữa, "blue" sau (giống Dutch National Flag).

Ví dụ: ["blue","green","blue","red","red"] → ['red','red','green','blue','blue'].

Giải thuật (Đếm và ghi đè - O(n) thời gian, O(1) không gian)

1. Khởi tạo 3 con trỏ: red = 0, green = 0, blue = 0.
2. Duyệt từng string trong strs:
   • Nếu "red": ghi đè strs[blue]="blue", ; strs[green]="green", ; strs[red]="red", .
   • Nếu "green": ghi đè strs[blue]="blue", ; strs[green]="green", .
   • Nếu "blue": ghi đè strs[blue]="blue", .
3. Trả về strs.

Ví dụ minh họa

class Solution:
    def solve(self, strs):
        green = blue = red = 0
        for string in strs:
            if string == "red":
                strs[blue] = "blue"; blue += 1
                strs[green] = "green"; green += 1
                strs[red] = "red"; red += 1
            elif string == "green":
                strs[blue] = "blue"; blue += 1
                strs[green] = "green"; green += 1
            elif string == "blue":
                strs[blue] = "blue"; blue += 1
        return strs

ob = Solution()
colors = ["blue","green","blue","red","red"]
print(ob.solve(colors))  # Output: ['red', 'red', 'green', 'blue', 'blue']

Đầu vào

["blue","green","blue","red","red"]

Đầu ra

['red', 'red', 'green', 'blue', 'blue']