Sắp xếp màu bằng Python

Giả sử chúng ta có một mảng với n đối tượng. Chúng có màu đỏ, trắng hoặc xanh lam, hãy sắp xếp chúng đúng vị trí để các đối tượng cùng màu nằm liền kề nhau. Vì vậy, với các màu theo thứ tự đỏ, trắng và xanh. Ở đây, chúng tôi sẽ sử dụng các số như 0, 1 và 2 để đại diện cho màu đỏ, trắng và xanh lam tương ứng. Vì vậy, nếu mảng giống như [2,0,2,1,1,0], thì đầu ra sẽ là [0,0,1,1,2,2]

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• đặt thấp:=0, giữa:=0 và cao:=độ dài của mảng - 1
• trong khi giữa <=cao
  • nếu arr [mid] =0, sau đó hoán đổi arr [mid] và arr [low], đồng thời tăng mức thấp và trung bình lên 1
  • ngược lại khi arr [mid] =2, hoán đổi arr [high] và arr [mid], giảm giá cao xuống 1
  • khác tăng giữa 1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách 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]