LEETCODE 75. Sort Colors 解题思路分析

题目大意：

颜色分类

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

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

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=75

解题思路分析：

题目要求使用一次循环的原地算法解决本题，本题的解题技巧在于如何使用双指针来变换某些位置上的数字来保证升序排序。

解题时，先定义两个指针red和blue，初始时red指向下标0，blue指向数组最后一位。然后再建立一个index从下标0开始循环数组的每一个数字。如果当前数字是0，那么交换当前下标与red指针指向的数字，red指针加一。此时能够保证red指针之前的数字都是0。

若当前数字是2，我们交换当前下标与blue指针指向的数字，然后blue下标减一，此时能够保证blue下标后面的数字都是2。这里需要注意一点，交换后，当前下标index值可能会变为0，1，2三种情况，因此我们还需要再次判断一下当前index，即需要index减一。

若当前数字是1，两个指针下标不变，index加一继续向后循环即可。

实现代码：

public void sortColors(int[] nums) {
    int red=0,blue=nums.length-1;
    for(int i=0;i<=blue;i++){
        if(nums[i]==0){
            nums[i]=nums[red];
            nums[red]=0;
            red++;
        }else if(nums[i]==2){
            nums[i]=nums[blue];
            nums[blue]=2;
            blue--;
            i--;
        }
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Colors.

Memory Usage: 42.1 MB, less than 5.51% of Java online submissions for Sort Colors.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-75-sort-colors-解题思路分析/