← 返回 snowflake 的题目列表Sort Colors in a RecordCollection In-Place
类型：online_judge
Problem: Sort Colors in a RecordCollection In-Place
You are given a RecordCollection class that internally stores a list of colors. Each color is represented by an integer:
0 means Red
1 means Green
2 means Blue
The RecordCollection already provides the following methods. You do not need to implement its internal storage:
getColor(i) -> int
Returns the color at index i.
swap(i, j) -> None
Swaps the colors at indices i and j.
Implement a function that sorts all colors in the RecordCollection in the order 0, 1, 2.
Requirements
Sort the collection in-place, using only getColor(i) and swap(i, j) to access or modify the collection.
Time complexity: O(n).
Extra space complexity: O(1).
You may not create another array and sort it.
Input Format
For testing purposes, assume the input is:
n
c1 c2 c3 ... cn
where n is the number of colors, and each color is one of 0, 1, or 2.
Output Format
Print the sorted colors separated by spaces.
Constraints
0 <= n <= 10^5
ci ∈ {0, 1, 2}
Example
Input:
6
2 0 2 1 1 0
Output:
0 0 1 1 2 2
Example
Input
6
2 0 2 1 1 0
Output
0 0 1 1 2 2