[LeetCode]75 Sort Colors
1895 ワード
https://oj.leetcode.com/problems/sort-colors/
http://blog.csdn.net/linhuanmars/article/details/24286349
http://blog.csdn.net/linhuanmars/article/details/24286349
public class Solution {
public void sortColors(int[] A)
{
// Solution A:
sortColors_CountColor(A);
// Solution B:
// sortColors_MergeSort(A, 0, A.length - 1);
}
///////////////////////////
// Solution A: CountColor
//
private void sortColors_CountColor(int[] A)
{
int[] c = new int[3];
for (int i : A)
{
c[i - 0] ++;
}
int count = 0;
int index = 0;
for (int i = 0 ; i < A.length ; i ++)
{
if (count == c[index])
{
count = 0;
index++;
i--;
continue;
}
A[i] = index;
count ++;
}
}
///////////////////////////
// Solution B: MergeSort
//
private void sortColors_MergeSort(int[] A, int low, int high)
{
if (low >= high)
return;
int mid = (low + high) / 2;
sortColors_MergeSort(A, low, mid);
sortColors_MergeSort(A, mid + 1, high);
// Merge
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
while (k < temp.length)
{
int a = i <= mid ? A[i] : Integer.MAX_VALUE;
int b = j <= high ? A[j] : Integer.MAX_VALUE;
if (a < b)
{
temp[k] = a;
i++;
}
else
{
temp[k] = b;
j ++;
}
k ++;
}
for (int m = low ; m <= high ; m ++)
{
A[m] = temp[m - low];
}
}
}