LeetCode] 色彩排序颜色排序 - 排序 - 循环不变式
最编程
2024-06-09 12:05:11
...
小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。
今天来刷一道经典的面试/笔试题,颜色分类也叫荷兰旗问题,因为荷兰的国旗是红白蓝这三个颜色,当然法国国旗、俄罗斯国旗这是这三种颜色~
75. 颜色分类【中等】
leetcode-cn.com/problems/so…
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
【解法一】两次遍历
一种很朴素的解法遍历两边,正着找0放在最前面,倒着找2放在最后面【双指针】
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
let first = 0;
let last = nums.length - 1;
// 第一次正序遍历,将所有的0 移动到最左边
for(let i = 0; i < nums.length; i++){
if(nums[i] === 0){
swap(nums, i, first);
first++;
}
}
// 第二次倒序遍历,把所有的2移动到最右边
for(let i = nums.length - 1; i >= 0; i--){
if(nums[i] === 2){
swap(nums, i, last);
last--;
}
}
};
function swap(nums,i,j){
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
也可以按顺序找,0放前面,1放中间,一样一样的【单指针】
var sortColors = function(nums) {
let first = 0
for(let i = 0; i < nums.length; i++){
if(nums[i] === 0){
swap(nums, i, first);
first++;
}
}
for(let i = first; i < nums.length; i++){
if(nums[i] === 1){
swap(nums, i, first);
first++;
}
}
};
【解法二】两层循环 冒泡排序
很多原地排序算法都可以【冒泡】【选择】【插入】等
更多关于排序算法可以参考这篇博文【算法】经典排序算法总结-JavaScript描述-图解-复杂度分析
var sortColors = function(nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length - i -1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
};
【解法三】遍历一次 + 循环不变量【重点】
头尾指针i
和j
,遇到0
与nums[i]
交换,遇到2
与nums[j]
交换,遇到1
就跳过啥也不做
定义循环不变量
[0, i) === 0
(i, k) === 1
(j, nums.length-1] === 2
终止条件是k===j
var sortColors = function(nums) {
let i = 0;
let j = nums.length - 1;
// 遍历一遍nums,到尾指针的位置
for(let k = 0; k <= j; k++){
if(nums[k] === 0){
// 遇到 0 和 头指针交换位置
swap(nums, k, i);
// 头指针后移
i++;
}else if(nums[k] === 2){
// 遇到 2 和 尾指针交换位置
swap(nums, k, j);
// 尾指针前移
j--;
// 循环指针后退一位,处理从后面移动过来的元素
k--;
}
}
};