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

---

文章目录

• 75. 颜色分类：
• 分析：
• 题解：

---

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)-1
	for 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) - 1
        while i <= r:
            if nums[i] < 1:
                if i == l:
                    i += 1
                else:
                    nums[i], nums[l] = nums[l], nums[i]
                l += 1
            elif nums[i] > 1:
                if i == r:
                    break
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1
            else:
                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;
            }
        }
    }
}

---

---