LeetCode75.SortColors

题目概述

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

题目大意

题目原意是，0,1,2分别代表是三个颜色的小球，让小球按照指定的顺序排列。
事实上，就是给一个数组进行排序。原地排序，不要使用额外的空间。

示例

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Note

You are not suppose to use the library’s sort function for this problem.

解答

看完题目的我？？？要想AC岂不是很简单：

var sortColors = function(nums) {
    nums.sort((a,b) => {
        return a-b
    })
};

Runtime: 44 ms, faster than 99.77% of JavaScript online submissions for Sort Colors.
Memory Usage: 33.8 MB, less than 80.88% of JavaScript online submissions for Sort Colors.

好了，目的并不在于此，手动滑稽~
备注中也让我们不要使用库的sort函数。

思路一：计数排序

首先，计算数组中0、1和2的个数
然后，根据这个个数覆盖原数组

var sortColors = function(nums) {
    let count0 = 0, count1 = 0, count2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {count0++;}
        if (nums[i] == 1) {count1++;}
        if (nums[i] == 2) {count2++;}
    }
    for(let i = 0; i < nums.length; i++) {
        if (i < count0) {nums[i] = 0;}
        else if (i < count0 + count1) {nums[i] = 1;}
        else {nums[i] = 2;}
    }
};

Runtime: 60 ms, faster than 80.76% of JavaScript online submissions for Sort Colors.
Memory Usage: 33.8 MB, less than 57.35% of JavaScript online submissions for Sort Colors.

思路二：One-pass

思路一用的是两次循环，那么是否能够使用一遍循环就完成呢？？
这才是题目想要我们实现的。

var sortColors = function(nums) {
    let count0 = -1, count1 = -1, count2 = -1;
    let len = nums.length;
	for(let p = 0; p < len; p++)
	{
		if(nums[p] == 0)
		{
			nums[++count2]=2;
			nums[++count1]=1;
			nums[++count0]=0;
		}
		else if (nums[p] == 1)
		{
			nums[++count2]=2;
			nums[++count1]=1;
			
		}
		else if (nums[p] == 2)
		{
			nums[++count2]=2;
		}
	}
};

Runtime: 52 ms, faster than 96.96% of JavaScript online submissions for Sort Colors.
Memory Usage: 33.8 MB, less than 67.44% of JavaScript online submissions for Sort Colors.

稍作优化：

var sortColors = function(nums) {
    let i = -1, j = -1, len = nums.length;
    for(let p = 0; p < len; p++) {
       let v = nums[p];
       nums[p] = 2;
       if (v == 0) {
          nums[++j] = 1;
          nums[++i] = 0;
       }
       else if (v == 1) {
           nums[++j] = 1;
       }
    }
};

Runtime: 48 ms, faster than 98.91% of JavaScript online submissions for Sort Colors.
Memory Usage: 33.8 MB, less than 78.99% of JavaScript online submissions for Sort Colors.

滑稽

每次做完看评论区，都很搞笑，hhhhhh~