题解 | #颜色分类#

题目分析

1. 题目给出了我们一个只包含0，1，2三种数字的列表
2. 题目要求我们将所有的0重新安排到列表左边，1在中间，2在右边，请返回重新组织后的列表

方法一：排序

• 实现思路

  • 调用sort()函数对列表直接排序可以得到最终结果

  • （在快速通过竞赛或者机试的时候可以用，但是并不是题目考察内容）

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param colors int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def sortColor(self , colors: List[int]) -> List[int]:
        # write code here
        colors.sort()    # 直接排序
        return colors

复杂度分析

• 时间复杂度：$O(nlogn)O(nlogn)$，排序的时间代价
• 空间复杂度：$O(1)O(1)$，引入常量级别的空间代价

方法二：三指针（类似快排中partition思路）

• 实现思路
  • 定义less指针代表列表中0和1数字的边界位置，初始化为-1
  • 定义more指针代表列表中1和2数字的边界位置，初始化为n（n为列表长度）
  • 定义一个cur指针对列表中的元素遍历

    • 当cur指向数字0的时候，将less += 1，并交换colors[cur]和colors[less]

    • 当cur指向数字2的时候，将more -= 1，并交换colors[cur]和colors[more]，然后将cur自减，是为了避免换过来的数字是0，下一轮循环需要重新将0放回less指定的范围内

    • 当cur指向数字1的时候，不做任何操作，等待cur自增即可

    • 每轮cur迭代自增，直到cur >= more停止

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param colors int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def sortColor(self , colors: List[int]) -> List[int]:
        # write code here
        n = len(colors)
        less = -1
        more = n
        cur = 0
        while cur < more:
            if colors[cur] == 0:
                less += 1
                # 交换位置
                temp = colors[less]
                colors[less] = colors[cur]
                colors[cur] = temp
            elif colors[cur] == 2:
                more -= 1
                #交换位置
                temp = colors[more]
                colors[more] = colors[cur]
                colors[cur] = temp
                #cur 回退，因为换过来的数字可能是0需要重新换到前面
                cur -= 1
            cur += 1
        return colors

复杂度分析

• 时间复杂度：$O(n)O(n)$，一次遍历的时间开销
• 空间复杂度：$O(1)O(1)$，只引入了常量级别的空间开销