LeeCode 75.颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

傻瓜式思路,因为要原地置换列表,所以选择列表切片的方式进行原地置换。

置换的边界就是统计0,1,2出现的次数。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 0 or len(nums)==1:
            nums = nums
        else:
            temp_0 = 0
            temp_1 = 0
            temp_2 = 0
            for i in nums:
                if i == 0:
                    temp_0+=1
                elif i == 1:
                    temp_1+=1
                elif i == 2:
                    temp_2+=1

            nums[:temp_0] = [0 for i in range(temp_0)]
            nums[temp_0:temp_0+temp_1] = [1 for i in range(temp_1)]
            nums[temp_0+temp_1:] = [2 for i in range(temp_2)]

傻瓜版的时间和空间不理想,想了一个进阶版


在《LeeCode 75.颜色分类》上留下第一个评论