千问 LeetCode 75. 颜色分类 Rust实现

LeetCode 75. 颜色分类Sort Colors是一道经典的算法题其核心本质是荷兰国旗问题Dutch National Flag Problem。题目要求在不使用库内置排序函数的情况下对包含 0、1、2 的数组进行原地排序。针对这道题主要有两种常见的 Rust 实现思路方法一三指针法最优解这是最精妙的解法。我们使用三个指针left 指向下一个 0 应该放置的位置right 指向下一个 2 应该放置的位置i 为当前遍历的指针。当遇到 0 时将其与 left 指向的元素交换然后 left 和 i 同时右移。当遇到 2 时将其与 right 指向的元素交换然后 right 左移注意此时 i 不能右移因为从右边交换过来的元素还未被检查过。当遇到 1 时不做处理i 直接右移。这种方法只需一次遍历时间复杂度为 O(n)空间复杂度为 O(1)。impl Solution {pub fn sort_colors(nums: mut Vec) {let (mut i, mut left, mut right) (0, 0, nums.len() - 1);while i right { if nums[i] 0 { nums.swap(i, left); left 1; i 1; } else if nums[i] 2 { nums.swap(i, right); if right 0 { break; } // 防止 usize 减法溢出 right - 1; // 注意这里 i 不增加因为从 right 换过来的元素还需要检查 } else { i 1; } } }}方法二计数排序法由于数组中的元素只有 0、1、2 三种我们可以先遍历一次数组统计这三种数字各自出现的次数。然后再遍历一次数组按照统计出的次数依次将 0、1、2 填回数组中。这种方法同样满足 O(n) 的时间复杂度和 O(1) 的空间复杂度且逻辑非常直观易懂。impl Solution {pub fn sort_colors(nums: mut Vec) {// 统计 0, 1, 2 出现的次数let mut count [0; 3];for num in nums.iter() {count[num as usize] 1;}// 根据统计结果重写数组 let mut index 0; for color in 0..3 { for _ in 0..count[color] { nums[index] color as i32; index 1; } } }}面试建议在实际面试中推荐优先使用方法一三指针法因为它完美展示了你对指针边界控制和原地数组操作的掌握程度是面试官最期望看到的解法。需要我帮你整理几道类似的荷兰国旗问题变体方便你顺带刷一下吗