Formatted question description: https://leetcode.ca/all/75.html
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. Example: Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] 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? @tag-array
The essence of this question is still a sorting question. The question gives a hint that it can be sorted by counting. You need to traverse the array twice. Then let’s look at this method first. Because there are only three different elements in the array, it is very easy to implement. easy.
- First traverse the original array and record the numbers of 0, 1, and 2 respectively.
- Then update the original array and assign 0, 1, 2 according to the number.
In the problem, it is necessary to traverse the array
only once to solve it, so you need to use a double pointer to do it, and move from the beginning and the end of the original array to the center.
- Define the red pointer to point to the beginning and the blue pointer to point to the end.
- Traverse the original array from the beginning,
- if it encounters 0, exchange the value and the value pointed to by the red pointer, and move the red pointer one bit backward.
- If it encounters 2, exchange the value and the value pointed to by the blue pointer, and move the blue pointer forward one bit. If it encounters 1, continue to traverse.