[Leetcode][python]Sort Colors/颜色分类

题目大意

给出一个由红、白、蓝三种颜色组成的数组,把相同颜色的元素放到一起,并整体按照红、白、蓝的顺序。用0表示红色,1表示白色,2表示蓝色。这题也称为荷兰国旗问题。

解题思路

参考: https://shenjie1993.gitbooks.io/leetcode-python/075%20Sort%20Colors.html

三指针:如果只有两种颜色,那么很容易想到一前一后两个指针向中间遍历,颜色不对就交换位置。三种颜色仍然可以这么做,只不过要多一个指针,前后两个指针用来分隔已经排好的红色和蓝色,中间的指针来遍历元素: 如果是红色,那么和前指针交换,并两个一起向后移,前指针换过来的一定是白色的,因为中指针已经扫描过那些元素了 如果是白色,那么继续向后移 如果是蓝色,那么和后指针交换,后指针向前移,中指针不能后移,因为此时不确定换过来的元素是什么颜色

代码

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left = mid = 0
        right = len(nums) - 1
        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                left += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1

总结

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小L的魔法馆

POJ 1113--Wall(计算凸包)

Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40363 ...

10330
来自专栏小L的魔法馆

2018 Wannafly summer camp Day3--Knight

Knight 题目描述: 有一张无限大的棋盘,你要将马从(0,0)(0,0)(0,0)移到(n,m)(n,m)(n,m)。 每一步中,如果马在(x,...

8030
来自专栏小L的魔法馆

POJ 1410--Intersection(判断线段和矩形相交)

Intersection Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

20030
来自专栏小L的魔法馆

2018 Wannafly summer camp Day8--区间权值

区间权值 小Bo有nnn个正整数a1a1a_1……anana_n,以及一个权值序列w1w1w_1……wnwnw_n,现在她定义f(l,r)=(∑ri=la2...

10050
来自专栏小L的魔法馆

HDU 6330--Visual Cube(构造,计算)

9250
来自专栏小L的魔法馆

HDU 6354--Everything Has Changed(判断两圆关系+弧长计算)

11150
来自专栏小L的魔法馆

atan和atan2反正切计算

返回值 若不出现错误,则返回 arg 在[−π/2;+π/2][−π/2;+π/2] [- π/2 ; +π/2] 弧度范围中的弧(反)正切( arctan...

27160
来自专栏小L的魔法馆

2018 Wannafly summer camp Day3--Shopping

Shopping 描述 题目描述: 你要买n件物品,其中有一些是凳子。

8720
来自专栏小L的魔法馆

2018 Wannafly summer camp Day3--Travel

Travel 描述 题目描述: 魔方国有n座城市,编号为1∼n1∼n1\sim n。城市之间通过n-1条无向道路连接,形成一个树形结构。

12630
来自专栏逍遥剑客的游戏开发

C#脚本实践(四): 反射与序列化

15250

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励