75. Sort Colors
Given an array nums 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.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
Example 1:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1] Output: [0,1,2]
Example 3:
Input: nums = [0] Output: [0]
Example 4:
Input: nums = [1] Output: [1]
Constraints:
n == nums.length1 <= n <= 300nums[i]is0,1, or2.
Follow up:
- Could you solve this problem without using the library's sort function?
- Could you come up with a one-pass algorithm using only
O(1)constant space?
Rust Solution
struct Solution;
impl Solution {
fn sort_colors(nums: &mut Vec<i32>) {
let n = nums.len();
let mut l = 0;
let mut r = n - 1;
let mut i = 0;
while i <= r {
while nums[i] == 2 && i < r {
nums.swap(i, r);
r -= 1;
}
while nums[i] == 0 && i > l {
nums.swap(i, l);
l += 1;
}
i += 1;
}
}
}
#[test]
fn test() {
let mut nums = vec![2, 0, 2, 1, 1, 0];
let res = vec![0, 0, 1, 1, 2, 2];
Solution::sort_colors(&mut nums);
assert_eq!(nums, res);
}
Having problems with this solution? Click here to submit an issue on github.