基数排序
解题思路
可以采用基数排序法的思想，用一个数组记录下 0、1、2 的次数，后重排，这个算法对数组进行了两次遍历；
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(1)
实现代码
var sortColors = function (nums) {
let num0 = 0;
let num1 = 0;
let num2 = 0;
let i = 0;
while (i < nums.length) {
if (nums[i] === 0) {
num0++;
} else if (nums[i] === 1) {
num1++;
} else {
num2++;
}
i++;
}
i = 0;
while (num0--) {
nums[i++] = 0;
}
while (num1--) {
nums[i++] = 1;
}
while (num2--) {
nums[i++] = 2;
}
};
三路快速排序
解题思路
-
设置三个 lt、gt、i 指针，定义：
nums[0...lt] == 0，nums[lt+1...i-1] = 1，nums[gt...n-1] == 2，遍历一遍改数列保持这个定义； -
也就是说：遇到 0 就排在前面，遇到 2 就排在最后面；
![]( "三路快速排序")
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(1)
实现代码
var sortColors = function (nums) {
let lt = 0;
let gt = nums.length - 1;
let inx = 0;
while (inx <= gt) {
if (nums[inx] === 0) {
[nums[lt++], nums[inx]] = [nums[inx], nums[lt]];
inx++; // inx 的位置是 0，要向后走，否则会一直进入这里
} else if (nums[inx] === 2) {
[nums[gt--], nums[inx]] = [nums[inx], nums[gt]];
} else {
inx++;
}
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1005. K 次取反后最大化的数组和
上一篇
评论
