daily leetcode - sort-colors - !
题目地址
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]
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 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--]);
}
}
}
};
当然我们也可以使用 while 循环的方式来写，那么就需要一个变量 cur 来记录当前遍历到的位置，参见代码如下：
解法三：
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]
*
* 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 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)
}
}
}
};
本文参考自：
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode
评论
