当前位置：首页 > news >正文

算法leetcode｜75. 颜色分类（rust重拳出击）

news 2025/7/30 7:03:04

文章目录

75. 颜色分类：
- 样例 1：
- 样例 2：
- 提示：
分析：
题解：
- rust：
- go：
- c++：
- python：
- java：

75. 颜色分类：

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

样例 1：

输入：nums = [2,0,2,1,1,0]输出：[0,0,1,1,2,2]

样例 2：

输入：nums = [2,0,1]输出：[0,1,2]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

分析：

面对这道算法题目，二当家的再次陷入了沉思。
感觉最直观的方式就是两次遍历，先从左到右遍历把红色都换到左边，再从右到左遍历把蓝色都换到右面，常数级的额外空间，O(n) 的时间复杂度，已经很优秀了吧，还要什么自行车，要什么手表，这么简单易懂。
但是算法就是要尽可能优化啊，没错，我们遍历了两次，能不能只遍历一次呢？
那就必须在一次遍历中同时将红色换到左边，并且把蓝色换到右面，有什么好的办法吗？注意到一个细节，题目中要求不能用内置的排序，为什么呢？优秀的排序算法的时间复杂度也要到 O(n*log n) 啊，还不如两次遍历呢，什么鬼？突然我转念一想，一般内置的排序算法都是 快速排序，然后想到快速排序中的一个片段，就是找到一个基准数，然后将小于基准数的元素都移动到基准数的左边，大于基准数的元素都移动到基准数的右边，怎么样，是不是豁然开朗？这不就是答案吗？
使用双指针分别放在头尾表示红色和蓝色的边界，然后遍历元素，如果是红色就交换到左边红色的边界并且移动这个红色的边界，如果是蓝色就交换到右边蓝色的边界并且移动这个蓝色的边界，如果是白色就不做处理继续遍历下一个元素。

题解：

rust：

impl Solution {pub fn sort_colors(nums: &mut Vec<i32>) {let (mut i, mut l, mut r) = (0, 0, nums.len() - 1);while i <= r {if nums[i] < 1 {if i == l {i += 1;} else {nums.swap(i, l);}l += 1;} else if nums[i] > 1 {if i == r {break;}nums.swap(i, r);r -= 1;} else {i += 1;}}}
}

go：

func sortColors(nums []int)  {i, l, r := 0, 0, len(nums)-1for i <= r {if nums[i] < 1 {if i == l {i++} else {nums[i], nums[l] = nums[l], nums[i]}l++} else if nums[i] > 1 {if i == r {break}nums[i], nums[r] = nums[r], nums[i]r--} else {i++}}
}

c++：

class Solution {
public:void sortColors(vector<int>& nums) {int i = 0, l = 0, r = nums.size() - 1;while (i <= r) {if (nums[i] < 1) {if (i == l) {++i;} else {swap(nums[i], nums[l]);}++l;} else if (nums[i] > 1) {if (i == r) {break;}swap(nums[i], nums[r]);--r;} else {++i;}}}
};

python：

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i, l, r = 0, 0, len(nums) - 1while i <= r:if nums[i] < 1:if i == l:i += 1else:nums[i], nums[l] = nums[l], nums[i]l += 1elif nums[i] > 1:if i == r:breaknums[i], nums[r] = nums[r], nums[i]r -= 1else:i += 1

java：

class Solution {public void sortColors(int[] nums) {int i = 0, l = 0, r = nums.length - 1;while (i <= r) {if (nums[i] < 1) {if (i == l) {++i;} else {int t = nums[i];nums[i] = nums[l];nums[l] = t;}++l;} else if (nums[i] > 1) {if (i == r) {break;}int t = nums[i];nums[i] = nums[r];nums[r] = t;--r;} else {++i;}}}
}