leetcode

Sort Colors

Sort Colors

Nice Version - 36ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i, j = 0, 0
        for k in range(len(nums)):
            v = nums[k]
            #print('i=%d, j=%d, v=%d--------' % (i, j, v))
            nums[k] = 2
            #print(nums)
            if v < 2:
                nums[j] = 1
                j += 1
            #print(nums)
            if v == 0:
                nums[i] = 0
                i += 1
            #print(nums)
            #print('i=%d, j=%d-------------\n' % (i, j))

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
In [27]: a = [2,0,2,1,1,0]
In [28]: s = Solution(); s.sortColors(a)
i=0, j=0, v=2--------
[2, 0, 2, 1, 1, 0]
[2, 0, 2, 1, 1, 0]
[2, 0, 2, 1, 1, 0]
i=0, j=0-------------
i=0, j=0, v=0--------
[2, 2, 2, 1, 1, 0]
[1, 2, 2, 1, 1, 0]
[0, 2, 2, 1, 1, 0]
i=1, j=1-------------
i=1, j=1, v=2--------
[0, 2, 2, 1, 1, 0]
[0, 2, 2, 1, 1, 0]
[0, 2, 2, 1, 1, 0]
i=1, j=1-------------
i=1, j=1, v=1--------
[0, 2, 2, 2, 1, 0]
[0, 1, 2, 2, 1, 0]
[0, 1, 2, 2, 1, 0]
i=1, j=2-------------
i=1, j=2, v=1--------
[0, 1, 2, 2, 2, 0]
[0, 1, 1, 2, 2, 0]
[0, 1, 1, 2, 2, 0]
i=1, j=3-------------
i=1, j=3, v=0--------
[0, 1, 1, 2, 2, 2]
[0, 1, 1, 1, 2, 2]
[0, 0, 1, 1, 2, 2]
i=2, j=4-------------
In [29]: a
Out[29]: [0, 0, 1, 1, 2, 2]

leet code