Easy | LeetCode 75. 颜色分类 | 快速排序
2021-03-06 20:27
标签：不可 public leetcode temp str ref jks ble 两个指针 给定一个包含红色、白色和蓝色，一共 此题中，我们使用整数 注意：请不要使用代码库中的排序函数来解决这道题。 进阶： 示例 1： 示例 2： 示例 3： 示例 4： 提示： 快速排序思想。这道题是，由计算机科学家 Edsger W. Dijkstra 首先提出的「荷兰国旗问题」。 第一次遍历先将0放到数组的头部, 接着第二次遍历从0的结尾地放1。 设置两个指针分别指向0的右边界和2的左边界。然后遍历数组, 当遍历到0时, 与0的右边界值交换, 并且0右边界和当前遍历指针均自增。当遍历到2时与2的左边界值交换, 此时, 仅仅递减2的左边界指针, 当前遍历指针在下次循环还是不变, 因为有可能把0和2继续从2的左边界交换回来。 Easy | LeetCode 75. 颜色分类 | 快速排序 标签：不可 public leetcode temp str ref jks ble 两个指针 原文地址：https://www.cnblogs.com/chenrj97/p/14289532.html75. 颜色分类
n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。0、 1 和 2 分别表示红色、白色和蓝色。
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
输入：nums = [2,0,1]
输出：[0,1,2]
输入：nums = [0]
输出：[0]
输入：nums = [1]
输出：[1]
n == nums.length1 nums[i] 为 0、1 或 2
解题思路
方法一： 快慢双指针 + 两次遍历
public void sortColors(int[] nums) {
int n = nums.length;
int ptr = 0;
for (int i = 0; i 方法二： 首尾双指针
所以从左到右的开始一段, 如果遇到2, 会交换到右边去, 如果遇到0, left和current会同步自增。所以当leftpublic void sortColors(int[] nums) {
// left的左边全部是0, right的右边全部是2
int left = 0, right = nums.length-1, mid= 0;
// 遍历当前数组
int current = left;
while (current
文章标题：Easy | LeetCode 75. 颜色分类 | 快速排序
文章链接：http://soscw.com/index.php/essay/61010.html