0075. 颜色分类 Sort Colors

问题描述

靠拢型双指针

靠拢型双指针是一种常用方法, 这个解法是它的变体, 叫DNF.

TODO(Shaohua): Add more description.

#![allow(unused)]
fn main() {
// 靠拢型双指针
// Dutch National Flag, DNF
// three-way partition
pub fn sort_colors1(nums: &mut Vec<i32>) {
    assert!(!nums.is_empty());

    // 双指针的变形, 三指针
    // left 用于指向数组中为0的元素的右侧
    let mut left = 0;
    // mid 用于遍历数组
    let mut mid = 0;
    // right 用于指向数组中为2的元素的左侧
    let mut right = nums.len() - 1;

    // 遍历数组
    while mid <= right {
        if nums[mid] == 0 {
            nums.swap(mid, left);
            mid += 1;
            // 左边的指针往右移一下
            left += 1;
        } else if nums[mid] == 2 {
            nums.swap(mid, right);
            // 右边的指针往左移一下
            if right > 0 {
                right -= 1;
            } else {
                break;
            }
        } else {
            mid += 1;
        }
    }
}
}

排序法

各种常见的排序算法都可以, 比如括入排序, 选择排序. 因为这毕竟是一个排序题.

#![allow(unused)]
fn main() {
// 选择排序 Selection Sort
pub fn sort_colors3(nums: &mut Vec<i32>) {
    for i in 0..(nums.len() - 1) {
        for j in i..nums.len() {
            if nums[i] > nums[j] {
                nums.swap(i, j);
            }
        }
    }
}
}