75. Sort Colors (Medium) Facebook Microsoft PocketGems
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?
Solution 1: 相向Two Pointers O(n); O(1)
这题和普通的相向双指针不太一样，比如3Sum遇到的双指针，在3Sum中，只需要左右两个双指针。
而这题还需要额外的一个指针来迭代数组，否则无法解决。
/**
* Two Pointers O(n);O(1) [1,2,0,0,1,2]
* The general idea is to Move red to the front, blue to the end. Keep white in the middle.
* One pointer to the end of red, redEnd, starting from 0.
* Another pointer to the start of blue, blueStart, starting from n-1, go backwards.
* For i = 0 to blueStart:
* | If nums[i] is RED:
* | Swap nums[i] with nums[redEnd].
* | Move redEnd.
* | Can move i too because the color swapped to i won't be red or blue.
* | If nums[i] is BLUE:
* | Swap nums[i] with nums[blueStart].
* | Move blueStart.
* | No need to move i since the color swapped to i can be blue or red.
* | If nums[i] is WHITE:
* | i++, just skip.
*/
public void sortColors(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
int left = 0; //point to the end of red, starting from 0.
int right = nums.length - 1; //point to the start of blue, starting from n-1
for (int i = 0; i <= right; i++) { //template, sort start color and end color
if (nums[i] == 0) {
//i++ cuz we know what we swap from left pointer is either 0 or 1, i's left side are all 0 and 1
swap(nums, i, left++);
} else if (nums[i] == 2) {
//can't i++ cuz we don't know what we swapped from right pointer, so we still need to check later
swap(nums, i--, right--);
}
}
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
Follow Up:
1.sort k colors [1,5,2,0,3,4,0,1,2]
/**
* follow up 1: sort k colors
* naive: counting sort, two-pass O(n) time, need O(k) space, but can be stable
* below: each time sort min&max, then sort middle part's min&max, until we sort all min&max,
* O(k/2 * n) time, O(1) space
*/
public void sortKColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = left; i <= right; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
for (int i = left; i <= right; i++) { //template, sort start color and end color
if (nums[i] == min) {
swap(nums, i, left++);
} else if (nums[i] == max) {
swap(nums, i--, right--);
}
}
}
}
public void sortColors2(int[] colors, int k) { //O(nlogk), the best algorithm based on comparing
if (colors == null || colors.length == 0) { //包括k种不同的颜色，并按照1到k进行编号
return;
}
rainbowSort(colors, 0, colors.length - 1, 1, k);
}
public void rainbowSort(int[] colors,
int left,
int right,
int colorFrom,
int colorTo) {
if (colorFrom == colorTo) {
return;
}
if (left >= right) {
return;
}
int colorMid = (colorFrom + colorTo) / 2;
int l = left, r = right;
while (l <= r) {
while (l <= r && colors[l] <= colorMid) {
l++;
}
while (l <= r && colors[r] > colorMid) {
r--;
}
if (l <= r) {
int temp = colors[l];
colors[l] = colors[r];
colors[r] = temp;
l++;
r--;
}
}
rainbowSort(colors, left, r, colorFrom, colorMid);
rainbowSort(colors, l, right, colorMid + 1, colorTo);
}
}
2.sort 3 categories
/**
* http://www.1point3acres.com/bbs/thread-209155-1-1.html
* follow up 2: sort 3 categories
* 给定一个API getCategory(int n)， return {L| M| H} 三种category
* 第一问 --- 给定一个Array， [4,2,5,7,8,9], 对于每一个int，有一个category，sort them by category
* 代码和原题基本一样，只需将nums[i]用API转换即可。
*/
public void sortCategories(int[] nums) {
int left = 0;
int right = nums.length - 1;
for (int i = 0; i <= right; i++) {
if (getCategory(nums[i]) == 0) { //0 should be 'L'
swap(nums, i, left++);
} else if (getCategory(nums[i]) == 2) { //2 should be 'H'
swap(nums, i--, right--);
}
}
}
private int getCategory(int num) {
return num;
}
3.sort k categories
/**
* follow up 3: sort k categories
* 第二问 ---- 如果这个时候有K个category， 应该怎么办？顺着上一题的思路，我的想法是将（0,1，。。。，k-1） category
* 分成（0）--> L, (1, k-2) -->M, (k-1) --> H，
* 然后相同的思想继续call之前的function，然后reduce为 （1，k-2）的range，重复之前的事情.
* 注：楼主的思路是可以的，但是代码有问题，直接修改sort k colors的代码即可。
*/
public void sortKCategories(int[] nums, int k) { //其实这里不需要k，根本没用到。
int left = 0;
int right = nums.length - 1;
while (left < right) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = left; i <= right; i++) {
min = Math.min(min, getCategory(nums[i]));
max = Math.max(max, getCategory(nums[i]));
}
for (int i = left; i <= right; i++) { //template, sort start color and end color
if (getCategory(nums[i]) == min) { //0 should be 'L'
swap(nums, i, left++);
} else if (getCategory(nums[i]) == max) { //2 should be 'H'
swap(nums, i--, right--);
}
}
}
}
public static void main(String[] args) {
SortColors test = new SortColors();
int[] nums = {3, 0, 5, 2, 1, 5, 3, 4, 2, 5}; //[0, 1, 2, 2, 3, 4, 3, 5, 5, 5]
// int[] nums = {3, 1, 2, 0, 1, 3, 2, 2, 4, 6, 7, 0, 1, 2};
test.sortKCategories(nums, 6);
System.out.print((Arrays.toString(nums)));
}
public void sortKCategories(int[] nums, int k) { //这份代码有问题，case跑不对 [0, 1, 2, 2, 3, 4, 3, 5, 5, 5]
int start = 0;
int end = k - 1;
while (start <= end) {
sortCategories(nums, start++, end--);
}
// while (k % 2 == 1 && start <= end) {
// sortCategories(nums, start++, end--);
// }
}
private void sortCategories(int[] nums, int start, int end) {
int left = 0;
int right = nums.length - 1;
while (getCategory(nums[left]) < start) { //skip nums that have been sorted
left++;
}
while (getCategory(nums[right]) > end) {
end--;
}
for (int i = left; i <= right; i++) {
if (getCategory(nums[i]) == start) {
swap(nums, i, left++);
} else if (getCategory(nums[i]) == end) {
swap(nums, i--, right--);
}
}
}