# 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. click to show follow up. Subscribe to see which companies asked this question.

# 分析

## 方法一

```void sortColors(int A[]) {
int n = A.length;
int num0 = 0, num1 = 0, num2 = 0;

for(int i = 0; i < n; i++) {
if (A[i] == 0) ++num0;
else if (A[i] == 1) ++num1;
else if (A[i] == 2) ++num2;
}

for(int i = 0; i < num0; ++i) A[i] = 0;
for(int i = 0; i < num1; ++i) A[num0+i] = 1;
for(int i = 0; i < num2; ++i) A[num0+num1+i] = 2;
}```

## 方法二

```// one pass in place solution
void sortColors(int A[]) {
int n = A.length;
int n0 = -1, n1 = -1, n2 = -1;
for (int i = 0; i < n; ++i) {
if (A[i] == 0)
{
A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
}
else if (A[i] == 1)
{
A[++n2] = 2; A[++n1] = 1;
}
else if (A[i] == 2)
{
A[++n2] = 2;
}
}
}```

## 方法三

```public void sortColors(int[] a) {
int n = a.length;
int second=n-1, zero=0;
for (int i=0; i<=second; i++) {
while (a[i]==2 && i<second) swap(a,i, second--);
while (a[i]==0 && i>zero) swap(a,i, zero++);
}
}```

0 条评论

• ### LeetCode 215. Kth Largest Element in an Array分析

显然最简单的思想就是排序，然后取出倒数第k个元素就可以了，我们可以直接调用内部的排序函数。

• ### [编程题] 赶去公司代码

终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，...

• ### LintCode整数排序题目分析解答选择排序插入排序小结

Given an integer array, sort it in ascending order. Use selection sort, bubble s...

• ### Lake Counting （POJ No.2386）

题意：有一个M*N的圈子，雨后有积水，然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

• ### 【HDU 4305】Lightning（生成树计数）

There are N robots standing on the ground (Don't know why. Don't know how).

• ### 数独终盘生成的几种方法

为了完成矩阵的转换，我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成：

• ### POJ-1088 滑雪 （记忆化搜索，dp）

滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

• ### HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...