# [LeetCode] 75. Sort Colors 颜色排序

2021年09月15日 阅读数：1

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.html

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.java

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

Example:数组

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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 a one-pass algorithm using only constant space?this

Java: one passhtm

```public class Solution {
public void sortColors(int[] nums) {
int left = 0, right = nums.length - 1;
int i = 0;
while(i <= right){
if(nums[i] == 0){
swap(nums, i, left);
left++;
i++; // 由于左边的已经检查过，因此能够进入下一个
} else if(nums[i] == 2){
swap(nums, i, right);
right--; // 由于交换过来的数还没检查过，因此不能i++
} else {
i++;
}
}
}

private void swap(int[] nums, int i1, int i2){
int tmp = nums[i1];
nums[i1] = nums[i2];
nums[i2] = tmp;
}
}
```

Python: one pass

```class Solution(object):
def sortColors(self, nums):
def triPartition(nums, target):
left, idx, right = 0, 0, len(nums) - 1

while idx <= right:
if nums[idx] < target:
nums[left], nums[idx] = nums[idx], nums[left]
left += 1
idx += 1
elif nums[idx] > target:
nums[idx], nums[right] = nums[right], nums[idx]
right -= 1
else:
idx += 1

triPartition(nums, 1)
```

Python:

```class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i, j, k = 0, 0, len(nums) - 1
while j <= k:  # while j < len(nums): or while j < k:
if nums[j] == 0:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j += 1  # important
elif nums[j] == 2:
nums[j], nums[k] = nums[k], nums[j]
k -= 1
else:
j += 1　　```

Python: one pass, no swap

```class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = j = 0
for k in xrange(len(nums)):
v = nums[k]
nums[k] = 2
if v < 2:
nums[j] = 1
j += 1
if v == 0:
nums[i] = 0
i += 1  　　```

C++: two pass, Time: O(n), Space: O(1)

```class Solution {
public:
void sortColors(int A[], int n) {
int count[3] = {0}, idx = 0;
for (int i = 0; i < n; ++i) ++count[A[i]];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < count[i]; ++j) {
A[idx++] = i;
}
}
}
};
```

C++: one pass, Time: O(n), Space: O(1)

```class Solution {
public:
void sortColors(int A[], int n) {
int red = 0, blue = n - 1;
for (int i = 0; i <= blue; ++i) {
if (A[i] == 0) {
swap(A[i], A[red++]);
} else if (A[i] == 2) {
swap(A[i--], A[blue--]);
}
}
}
};
```

C++:

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

[LeetCode] 15. 3Sum 三数之和