75. Sort Colors

向右看齐 2022-02-09 07:53 189阅读 0赞

Given an array with *n* objects colored red, white or blue, sort them **[in-place][] **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.

**Example:**

Input: [2,0,2,1,1,0]
    Output: [0,0,1,1,2,2]

**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 a one-pass algorithm using only constant space?

解题思路：

其实题目的要求很简单，就是将一个仅包含0，1，2的数组进行排序，但是更高的要求时只是用常数空间，以及仅用一趟扫描。  
所以这两个要求就禁止了大多数的排序算法。好在这个数组只有三个数字0，1，2，也就是说排序后，数组的前面肯定都是0，后面都是2，中间都是1，这一点时可以确定的。那么就有这样一种思路，就是遍历数组，如果是0，就移到前面，如果是2就移到后面，剩下中间的就是1了。  
所以我的方法 就是使用双指针first和last。first指针就是将要替换成0的位置，last指针就是要替换成2的位置。接下来遍历数组，如果是0，先看当前位置是否大于first，如果相等，说明此位置之前都是0，因此不要操作，first加1后接着遍历；如果当前位置大于first，则要进行交换。将0换到first指向的位置，当前位置的值因此也变化了，成为1（只可能是1，因为此位置之前的2全部都已经处理了），first加1接着遍历。  
如果遍历到了2，当前位置与last比较，如果last指向的也是2，那么last减去1，不然又将会把2换到前面，本程序会导致死循环。如果last不等于2，那么交换两个值，并且last减去1。但是此时还不能接着遍历，因为此时交换回来的值可能是0，可能还会再与first比较。  
如果遍历值是1，不用管继续遍历。  
当遍历的位置等于last的时候，就可以退出遍历了，因为last后面都是2，不用比较了。

class Solution:
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            first = 0
            last = len(nums) - 1
            i = 0
            while i < last:
                if nums[i] == 0:
                    if i > first:
                        nums[first], nums[i] = nums[i], nums[first]
                    i += 1
                    first += 1
                elif nums[i] == 2:
                    if nums[last] != 2:
                        nums[last], nums[i] = nums[i], nums[last]
                    last -= 1
                else:
                    i += 1

[in-place]: https://en.wikipedia.org/wiki/In-place_algorithm