【LeetCode刷题之旅】75 Sort Colors【C++】
听老师讲课,把所述的两种方法记录下来。
第一种是暴力解法:
class Solution {
public:
//时间复杂度:O(n)
//空间复杂度:O(k),k为元素的取值范围
void sortColors(vector<int>& nums) {
int count[3] = {0}; //存放0,1,2三个元素的频率的数组
for (int i = 0; i < nums.size(); i++){
assert(nums[i] >= 0 && nums[i] <= 2);
count[nums[i]] ++;
}
int index = 0;
for (int i = 0; i< count[0];i++)
nums[index++] = 0;
for (int i = 0; i< count[1];i++)
nums[index++] = 1;
for (int i = 0; i< count[2];i++)
nums[index++] = 2;
}
};
第二种是三路快排:
class Solution {
public:
//时间复杂度:O(n)
//空间复杂度:O(1)
//只遍历了一遍
void sortColors(vector<int>& nums) {
int zero = -1; // nums[0...zero] = 0,设置为-1表示此区间此时无效,没有任何一个元素
int two = nums.size(); // nums[two...n-1] = 2,设置为nums.size()而不是num.size()-1,是因为此时无效
for ( int i = 0; i< two ; ){
if ( nums[i] == 1)
i++;
else if (nums[i] == 2){
two --;
swap( nums[i] , nums[two]); //这两句也可合并成为: swap( nums[i] , nums[--two])
}
else{ // nums[i] == 0
assert(nums[i] == 0); //捕捉其他数值的异常输入
zero ++;
swap( nums[zero] , nums[i]); //这三句可写成 swap( nums[++zero] , nums[i++])
i++;
}
}
}
};
很奇怪,明明只遍历了一遍数组,时间却比暴力解法还要多。。。
还希望大佬告诉我下……