Python 中的对颜色进行排序

假设我们有一个包含 n 个对象的数组。这些对象被染成了红色、白色或蓝色，请对它们进行就地排序，以便同颜色的对象相邻。颜色按红、白、蓝的顺序。这里，我们将使用 0、1 和 2 分别表示红色、白色和蓝色。因此，如果数组为 [2,0,2,1,1,0]，则输出将为 [0,0,1,1,2,2]

要解决这个问题，我们将遵循以下步骤 −

  • 设置低 := 0、中 := 0 和高 := 数组长度 – 1
  • 当 mid <= high 时
    • 如果 arr[mid] = 0，则交换 arr[mid] 和 arr[low]，并使 low 和 mid 均加 1
    • 否则，当 arr[mid] = 2 时，交换 arr[high] 和 arr[mid]，使 high 减 1
    • 否则，将 mid 加 1

示例（Python）

让我们看看以下实现以获得更好的理解 −

 动态演示

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]))

输入

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

输出

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

更新于：2020 年 4 月 27 日

2K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始
广告