Leetcode 75. Sort Colors

https://leetcode.com/problems/sort-colors/

Medium

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?

Dutch national flag problem。类似快排的three-way-partition。用三个指针，保证0 <= i <= j <= n <= len(array) - 1，i 是小于middle的元素的最大下标，n是大于middle的元素的最小下标，j是当前元素下标。最终划分成 [0, i], (i, n), [n, len(array) - 1]。
Python O(n) 1 pass in-place solution with explanation - LeetCode Discuss
- https://leetcode.com/problems/sort-colors/discuss/26481/Python-O(n)-1-pass-in-place-solution-with-explanation
Dutch national flag problem - Wikipedia
- https://en.wikipedia.org/wiki/Dutch_national_flag_problem

 1 class Solution:
 2     def sortColors(self, nums: List[int]) -> None:
 3         """
 4         Do not return anything, modify nums in-place instead.
 5         """
 6         
 7         def three_way_partition(nums, middle):
 8             i, j, n = 0, 0, len(nums) - 1
 9             
10             while j <= n:
11                 if nums[j] < middle:
12                     nums[i], nums[j] = nums[j], nums[i]
13                     i += 1
14                     j += 1
15                 elif nums[j] > middle:
16                     nums[j], nums[n] = nums[n], nums[j]
17                     n -= 1
18                 else:
19                     j += 1
20         
21         three_way_partition(nums, 1)

View Python Code