leetcode: 75. Sort Colors

Problem

# Given an array with n objects colored red, white or blue, 
# sort them so that objects of the same color are adjacent,
# with the colors in the order red, white and blue.
#
# Here, we will use the integers 0, 1, and 2 
# to represent the color red, white, and blue respectively.
#
# Note:
# You are not suppose to use the library's sort function for this problem.
#
# click to show follow up.
#
# Follow up:
# A rather straight forward solution is a two-pass algorithm using counting sort.
# First, iterate the array counting number of 0's, 1's, and 2's, 
# then overwrite array with total number of 0's,
# then 1's and followed by 2's.
# Could you come up with an one-pass algorithm using only constant space?

Idea

1.由于x[:red+1]都是被white指针滑过的区域,保证了x[red]一定为0,
所以当 x[white]==0 时,white和red同步加1;

2.而x[blue:]尚未被white指针滑过,所以无法保证了x[blue]一定为2,
因此当 x[white]==2 时,只有white加1;

3.注意循环条件是 white <= blue 。

AC

class Solution():
    def sortColors(self, x):
        red, white, blue = 0, 0, len(x)-1
        while white <= blue:
            if x[white] == 0:
                x[red], x[white], white, red = x[white], x[red], white+1, red+1
            elif x[white] == 1:
                white += 1
            else:
                x[white], x[blue], blue = x[blue], x[white], blue-1


if __name__ == "__main__":
    x = [2, 1, 1, 0, 0, 2]
    Solution().sortColors(x)
    assert x == [0, 0, 1, 1, 2, 2]

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the resul...

1995
来自专栏项勇

笔记26 | 总结Android的获取系统时间的几种方法

1955
来自专栏前端迷

数据结构与前端开发(四)-树

二叉树拥有一个根节点,每个节点至多拥有两个子节点,分别为:左节点和右节点。树的最底部节点称之为叶节点,当一颗树的叶数量数量为满时,该树可以称之为满二叉树。

1953
来自专栏数据处理

leetcode222求完全二叉树节点个数

3714
来自专栏木子昭的博客

明星程序员被Google挂掉的故事

首先要提一个软件Homebrew Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore ? ...

3755
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

1012
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构之单链表线性存储实现 Beta

正文之前 ? 昨天晚上阶段性的完成了一部分数学的复习,所以今天打算撸一撸代码,然后发现提电脑忘指针。所以自己磕磕盼盼,对照了一下网上的代码,总算把线性存储单链表...

36211
来自专栏函数式编程语言及工具

Scalaz(33)- Free :算式-Monadic Programming

在任何模式的编程过程中都无法避免副作用的产生。我们可以用F[A]这种类型模拟FP的运算指令:A是可能产生副作用的运算,F[_]是个代数数据类型ADT(Alg...

1637
来自专栏算法修养

FZU 1064 教授的测试(卡特兰数,递归)

Problem 1064 教授的测试 Accept: 149 Submit: 364 Time Limit: 1000 mSec Memor...

3628
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1161

扫码关注云+社区

领取腾讯云代金券