Intermediate Level
Implement the sortColorsOnePass method that sorts three color values in one pass.
The input contains an array nums and its length size. The array contains only three values: 0, 1, and 2.
Your task is to reorder the array so that all 0 values come first, followed by all 1 values, and then all 2 values.
For example, [2,0,2,1,1,0] should become [0,0,1,1,2,2].
Example 1
Input
nums (int[]) =
[2,0,2,1,1,0]size (int) =
6Returns (int[])
[0,0,1,1,2,2]Example 2
Input
nums (int[]) =
[2,0,1]size (int) =
3Returns (int[])
[0,1,2]Example 3
Input
nums (int[]) =
[0]size (int) =
1Returns (int[])
[0]Use the Dutch National Flag one-pass algorithm.
Maintain three areas: values before low are already 0, values after high are already 2, and mid scans the unknown area.
When nums[mid] is 0, swap it to the front. When it is 2, swap it to the back. When it is 1, just move forward.
Pseudocode:
function sortColorsOnePass(nums, size):
low = 0
mid = 0
high = size - 1
while mid <= high:
if nums[mid] == 0:
swap nums[low] and nums[mid]
low++
mid++
else if nums[mid] == 1:
mid++
else:
swap nums[mid] and nums[high]
high--
return numsReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run