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.

You must solve this problem without using the library’s sort function.

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]

Dutch National Flag (three-way partition):

#![allow(unused)]
fn main() {
// Dutch National Flag algorithm
// time O(n), space O(1)
pub fn sort_colors(nums: &mut Vec<i32>) {
    let mut i: usize = 0;
    let mut l: usize = 0;
    let mut r: usize = nums.len();
    while i < r {
        if nums[i] == 0 {
            nums.swap(l, i);
            l += 1;
            i += 1;
        } else if nums[i] == 2 {
            r -= 1;
            nums.swap(i, r);
        } else {
            i += 1;
        }
    }
}
}

Counting sort (bucket):

#![allow(unused)]
fn main() {
// time O(n), space O(1)
pub fn sort_colors_bucket(nums: &mut Vec<i32>) {
    let mut cnt = [0; 3];
    for &num in nums.iter() {
        cnt[num as usize] += 1;
    }

    let mut idx: usize = 0;
    for i in 0..3 {
        while cnt[i] > 0 {
            cnt[i] -= 1;
            nums[idx] = i as i32;
            idx += 1;
        }
    }
}
}