您现在的位置是:首页 >其他 >Leetcode-day2【75】颜色分类网站首页其他

Leetcode-day2【75】颜色分类

MSTIFIY 2023-05-28 12:00:02
简介Leetcode-day2【75】颜色分类

75.颜色分类

题目

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

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

解题思路

读完题目,最容易想到的通用解法便是直接对数组进行排序。这里使用插入排序算法。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(1,n):
            for j in range(i,0,-1):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
                else:
                    break

插入排序算法大致思路如下:该算法不断维护一个有序数组,我们假设前i个数是升序(降序)排列,我们将i1逐渐增大至原来数组的大小n时,那么我们便会得到原来数组的排序结果。在i增大的每个循环中,我们需要把第i个数(待插入的数)拿出来,将其与前面的一个数进行比较,如果小于(大于)便交换两个数,循环这个过程,直到前面一个数不满足前面的条件为止,即说明此时该元素的位置符合整个前i个数的升序(降序)排列。

复杂度分析

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( 1 ) O(1) O(1)

解题思路【学习】

75. 颜色分类(官方题解)

partition

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NpWhBEtE-1681999331792)(C:UsersMSTIFIYAppDataRoamingTypora ypora-user-imagesimage-20230420205617921.png)]

本算法的关键在于对分区定义的遵循,也称循环不变量。 注意,在最开始,应该使每个区间为空。循环变量i指向待划分的元素。

from typing import List
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def swap(nums, index1, index2):
            """交换两个元素的位置"""
            nums[index1], nums[index2] = nums[index2], nums[index1]

        n = len(nums)
        if n < 2:
            """对于元素个数小于2的数组不需要排序"""
            return
        # all in [0, p0) == 0
        # all in [p0, i) == 1
        # all in (p2, n - 1] == 2
        p0 = 0
        i = 0
        p2 = n - 1
        
        while i <= p2:
            if nums[i] == 0:
                swap(nums, i, p0)
                i += 1
                p0 += 1
            elif nums[i] == 1:
                i += 1
            else:
                swap(nums, i, p2)
                p2 -= 1

作者:liweiwei1419
链接:https://leetcode.cn/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。