## 题目地址

https://leetcode.com/problems/sort-colors/

## 题目描述

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.

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.

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?

## 思路

• 首先遍历一遍原数组，分别记录 0，1，2 的个数。
• 然后更新原数组，按个数分别赋上 0，1，2。

``````class Solution {
public:
void sortColors(vector<int>& nums) {
vector<int> colors(3);
for (int num : nums) ++colors[num];
for (int i = 0, cur = 0; i < 3; ++i) {
for (int j = 0; j < colors[i]; ++j) {
nums[cur++] = i;
}
}
}
};

``````

• 定义red指针指向开头位置，blue指针指向末尾位置。

• 从头开始遍历原数组，如果遇到0，则交换该值和red指针指向的值，并将red指针后移一位。若遇到2，则交换该值和blue指针指向的值，并将blue指针前移一位。若遇到1，则继续遍历。

``````class Solution {
public:
void sortColors(vector<int>& nums) {
int red = 0, blue = (int)nums.size() - 1;
for (int i = 0; i <= blue; ++i) {
if (nums[i] == 0) {
swap(nums[i], nums[red++]);
} else if (nums[i] == 2) {
swap(nums[i--], nums[blue--]);
}
}
}
};

``````

``````class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0, right = (int)nums.size() - 1, cur = 0;
while (cur <= right) {
if (nums[cur] == 0) {
swap(nums[cur++], nums[left++]);
} else if (nums[cur] == 2) {
swap(nums[cur], nums[right--]);
} else {
++cur;
}
}
}
};
``````

### 思路2

• 其实就是排序，而且没有要求稳定性，就是用啥排序算法都行。
• 题目并没有给出数据规模，因此我默认数据量不大，直接选择了冒泡排序

## 关键点解析

• 冒泡排序的时间复杂度是N平方，无法优化，但是可以进一步优化常数项，
• 比如循环的起止条件。 由于每一次遍历都会将最后一位“就位”，因此内层循环的截止条件就可以是`nums.length - i`， 而不是 `nums.length`, 可以省一半的时间。

## 代码

``````/*
* @lc app=leetcode id=75 lang=javascript
*
* [75] Sort Colors
*
* https://leetcode.com/problems/sort-colors/description/
*
* algorithms
* Medium (41.41%)
* Total Accepted:    297K
* Total Submissions: 716.1K
* Testcase Example:  '[2,0,2,1,1,0]'
*
* 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.
*
* 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.
*
* 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?
*
*
*/
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
function swap(nums, i, j) {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - i; j++) {
if (nums[j] < nums[j -1]) {
swap(nums, j - 1 , j)
}

}
}
};
``````

评论
0 评论