【python】LeetCode | 您所在的位置:网站首页 › 荷兰桔梗 › 【python】LeetCode |
参考博客:http://blog.csdn.net/sunnyyoona/article/details/43488481 思路采取原作者,但代码转为了python。代码参考了链接:http://www.cnblogs.com/zuoyuan/p/3775832.html
【问题】
现有红白蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题,是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。 【分析】这个问题我们可以将这个问题视为一个数组排序问题。红白蓝分别对应数字0、1、2。红、白、蓝三色小球数量并不一定相同。 【思路一(桶排序/计数排序)】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. (1)遍历数组,统计红白蓝三色球(0,1,2)的个数 (2)根据红白蓝三色球(0,1,2)的个数重排数组 时间复杂度:O(n) 【代码一】 class Solution(object): def sortColors(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ bucket=[0]*3 for i in nums: bucket[i]+=1 del nums[:] for j in range(3): for k in range(bucket[j]): nums.append(j) 【思路二】我们可以把数组分成三部分,前部(全部是0),中部(全部是1)和后部(全部是2)三个部分,每一个元素(红白蓝分别对应0、1、2)必属于其中之一。 将前部和后部各排在数组的前边和后边,中部自然就排好了。 设置两个指针begin指向前部的末尾的下一个元素(刚开始默认前部无0,所以指向第一个位置),end指向后部开头的前一个位置(刚开始默认后部无2,所以指向最后一个位置),然后设置一个遍历指针current,从头开始进行遍历。 (1)若遍历到的位置为1,则说明它一定属于中部,根据总思路,中部的我们都不动,然后current向前移动一个位置。 (2)若遍历到的位置为0,则说明它一定属于前部,于是就和begin位置进行交换,然后current向前移动一个位置,begin也向前移动一个位置(表示前边的已经都排好了)。 (3)若遍历到的位置为2,则说明它一定属于后部,于是就和end位置进行交换,由于交换完毕后current指向的可能是属于前部的,若此时current前进则会导致该位置不能被交换到前部,所以此时current不前进。而同1),end向前移动一个位置。 |
CopyRight 2018-2019 实验室设备网 版权所有 |