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.
#
# 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?

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 。

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]