导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一:库函数……
    2. 方法二:分别统计三种颜色数量,然后遍历赋值
    3. 方法三

LeetCode-75.Sort Colors

题目

Given an array with n objects colored red, white or blue, sort them 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.

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

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

翻译

给出一个包含n个物体的数组,分别被涂成了红色、白色和蓝色,将它们排序,使得相同颜色的物体相邻,顺序为红色、白色和蓝色。
在这里我们用整数0、1和2来分别代表红色、白色和蓝色。
注意:你不应当使用库排序函数来解本题。
跟进:一个较为直接的解法是两趟遍历数组,计数0、1和2的个数,然后逐个对数组中的数字赋值。
你能给出只使用常数空间的一趟遍历的算法吗?

方法一:库函数……

1
2
3
4
5
public class Solution {
public void sortColors(int[] nums) {
Arrays.sort(nums);
}
}

方法二:分别统计三种颜色数量,然后遍历赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public void sortColors(int[] nums) {
int red = 0, white = 0, blue = 0;
for (int num : nums) {
switch (num) {
case 0:
red++;
break;
case 1:
white++;
break;
case 2:
blue++;
break;
}
}
int index = 0;
while (red-- > 0) nums[index++] = 0;
while (white-- > 0) nums[index++] = 1;
while (blue-- > 0) nums[index++] = 2;
}
}

方法三

设立两个指针firstNotRed和lastNotBlue。
firstNotRed指向第一个不是0的元素,lastNotBlue指向最后一个不是2的元素。初始时分别指向数组头尾。
从头遍历数组,当遇到0时,与firstNotRed交换,并更新firstNotRed;当遇到2时,与lastNotBlue交换,并更新lastNotBlue,同时遍历指针回退,继续处理交换过来的值。
时刻保证firstNotRed左边的值都为0,lastNotBlue后面的值都为2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public void sortColors(int[] nums) {
int firstNotRed = 0, lastNotBlue = nums.length - 1;
for (int i = 0; i <= lastNotBlue; i++) {
if (nums[i] == 0) {
nums[i] = nums[firstNotRed];
nums[firstNotRed] = 0;
firstNotRed++;
} else if (nums[i] == 2) {
nums[i] = nums[lastNotBlue];
nums[lastNotBlue] = 2;
lastNotBlue--;
i--;
}
}
}
}

参考:
https://segmentfault.com/a/1190000003761919
http://blog.csdn.net/doc_sgl/article/details/12007965