解
第一步，万年不变的查错。如果给的array是null或不够两个数，直接return 0
public void sortColors(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
...
}
这个题其实就是排序，暴力破解普通的就O(nlogn)，因为这是一组数字，所以可以用对数字比较高效的计数排序（Counting Sort)。我之前也没听过这个排序算法。大意是
计数排序.gif
在做这道题的时候，因为我们知道只有3个数，所以解法相对简单。先创建一个长度为3的array counts用来存放3个颜色的个数，然后遍历一遍array来算出count。
int[] counts = new int[3];
for (int num : nums) {
counts[num]++;
}
然后就可以遍历一遍counts，直接覆盖原来的array。这个double for loop看起来慢，但其实所有次数加起来等于array的长度，因为他就是把每一个element访问一遍，改掉它的数值而已。
int current = 0;
for(int i = 0; i < counts.length; i++) {
for (int j = 0; j < counts[i]; j++) {
nums[current++] = i;
}
}
完整的code
public class Solution {
/*
* @param nums: A list of integer which is 0, 1 or 2
* @return: nothing
*/
public void sortColors(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
int[] counts = new int[3];
for (int num : nums) {
counts[num]++;
}
int current = 0;
for(int i = 0; i < counts.length; i++) {
for (int j = 0; j < counts[i]; j++) {
nums[current++] = i;
}
}
}
}
解2
这道题真正的挑战是不用额外的memory。一般array不用多余的memory的话，就得用多个pointer了吧。两个pointer我也知道，但是怎么用挺绕弯。先来初始化一下左右两个pointer。
int left = 0;
int right = nums.length - 1;
接下里的关键就是，再用一个pointer来做当前指针。这样，左边的只管0，右边的只管2，当前的管1。
int current = 0;
这样，当current小于等于right的时候，不断的去交换。如果发现当前是0，就跟左边交换，如果发现当前是2，就跟右边交换。如果当前是1，那就把 current往前移动。关键在于怎么处理每个condition里面pointer的移动。
while (current <= right) {
...
}
当现在的是0的时候，我们把它和左边交换，因为前面已经sort过，这个时候它只可能是0或1，所以current可以移动。而交换了以后，left肯定是0了，所以left也要往前移一个。
if (nums[current] == 0) {
swap(nums, current, left);
left++;
current++;
}
当现在的是2的时候，我们把它和右边交换。因为我们是从左往右，所以右边是什么都有可能，0，1，2都是有可能被换过来的。所以这个时候current不能动，而right肯定是2了，所以right可以往左移一个。这样即使current又被换成了2，right变了，我们也不会陷入死循环。
else if (nums[current] == 2) {
swap(nums, current, right);
right--;
}
当现在的是1的时候，我们直接跳过，因为只有3个数字，0都被归到左边了，2都被归到右边了，剩下的1肯定就是在中间了。
else {
current++;
}
所以left的左边代表着全部都是0，right的右边代表的全部都是2。当current > right的时候，意味着我们在1的最右边了，所以排序完成，就可以结束了。
这里还用到了一个swap，就是最普通的交换。
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
完整的code
public class Solution {
/*
* @param nums: A list of integer which is 0, 1 or 2
* @return: nothing
*/
public void sortColors(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
int left = 0;
int right = nums.length - 1;
int current = 0;
while (current <= right) {
if (nums[current] == 0) {
swap(nums, current, left);
left++;
current++;
} else if (nums[current] == 2) {
swap(nums, current, right);
right--;
} else {
current++;
}
}
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
分析
时间复杂度
第一个解法，遍历了2次，所以O(n) （严格来说是2n，但是Big O Notation是不需要管那个2的）。
第二个解法，两个pointer，从未交叉，一次遍历，所以是O(n)。
相比之下，第二个解法在时间复杂度上更好。
空间复杂度
第一个解法需要一个长度为k的array来放count，这里k是3。所以空间复杂度的话，应该是O(k)。
第二个解法，不需要任何额外的空间，所以是O(1)。
相比之下，还是第二个解法好一点。
就以这道题而言，应该还是考第二个解法，但可以从第一个解法开始说起，慢慢优化到第二个解法。
网友评论