LeetCode 75 颜色排序

1 题目描述

给定一个数组,该数组有N个对象,每个对象被标记为红、白、蓝三种颜色中的某一种。对该对象数组进行排序,使相同颜色的对象连在一起,分别为红色部分,白色部分,蓝色部分。

这里,我们将数字1,2,3分别代表红,白,蓝。

注:请勿使用sort库函数。

例子:

输入:[2,0,2,1,1,0]

输出:[0,0,1,1,2,2]

进阶:

  • a)一个直接的解法是先计数再排序,使用了两次遍历来实现,即先遍历一次数组算出所有1,2,3的个数,然后再遍历一次,分别将对应个数的1,2,3填进去;

  • b)您能否提出一种一次遍历且使用常数空间的算法。

题目出处:LeetCode

2 解决思路

总体思路为:遍历数组,遇到0,将其排到头部,遇到2,则将其排到尾部,这样遍历一次即可将3类数都排好。

下面为具体步骤:

  • a)首先申请3个变量,i、start与end,i为当前元素指针,用start标记头部1的头,end标记尾部2的头。

  • b)从头遍历数组,若i指的元素为0,若其前边有1(即i>start),则与start对应的1的头交换,然后start后移,i也后移;若其前边没有1,无需处理,start和i后移即可。

  • c)若i指的元素为2,则看其与end对应元素比谁大,若其比end对应元素大,则两元素交换,然后end前移一位;若其与end对应元素相等,end亦前移一位。

  • d)若i指的元素为1,仅i后移,去查看下一个元素。

  • e)i遍历至end的位置,则完成排序。

整个算法时间复杂度为O(N),空间复杂度为O(1)。

3 Golang实现代码

https://github.com/olzhy/

func sortColors(nums []int) {
    swap := func(nums []int, i, j int) {
        nums[i], nums[j] = nums[j], nums[i]
    }

    start, end := 0, len(nums)-1
    for i := start; i <= end; {
        switch nums[i] {
        case 0:
            if start < i {
                swap(nums, i, start)
            }
            start++
            i++
        case 1:
            i++
        case 2:
            if nums[end] < 2 {
                swap(nums, i, end)
            }
            end--
        }
    }
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝