leetcode 75. Sort Colors

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.

题意:一个数组,由0,1,2组成,现在要求升序排列

思路:无脑做法就是计数排序,扫两遍,时间复杂度O(n),空间复杂度O(1)

如果只扫一遍呢?

一个容易想到的思路是两个指针:

需要注意 的是,交换2后要再次遍历到当前位置,或者说,只有当不交换2的时候,才执行cur++

 

 

 

还有一个神奇的思路:r,w,b分别表示下一个对应颜色要放的位置。

如果当前是0,那么0,1,2都要后移一个。

如果当前是1,那么1,2的位置需要后移。

如果当前是2,那么2的位置需要后移。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz