网站建设与制作教程吕磊,潍坊在线制作网站,申请网站域名要多少钱,上海建设工程招投标在什么网站颜色分类 题解1 双指针题解2 单指针 给定一个包含红色、白色和蓝色、共
n 个元素的数组
nums #xff0c;原地对它们进行排序#xff0c;使得相同颜色的元素相邻#xff0c;并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在… 颜色分类 题解1 双指针题解2 单指针 给定一个包含红色、白色和蓝色、共
n 个元素的数组
nums 原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1 输入nums [2,0,2,1,1,0] 输出[0,0,1,1,2,2]
示例 2 输入nums [2,0,1] 输出[0,1,2]
提示
n nums.length1 n 300nums[i] 为 0、1 或 2
题解1 双指针
class Solution {
public:void sortColors(vectorint nums) {const int s nums.size();// 0对应的位置1对应的位置int p0, p1;p0 p1 0;for(int i 0; i s; i){if(1 nums[i]){swap(nums[i], nums[p1]);p1 ;}else if(0 nums[i]){swap(nums[i], nums[p0]);// 1比0多说明p0位置是1if(p0 p1){// 把1换回来swap(nums[i], nums[p1]);}// 多了个0p1的位置也往后指了p0 ;p1 ;} }return;}
};题解2 单指针
class Solution {
public:void sortColors(vectorint nums) {const int s nums.size();// 0对应的位置1对应的位置int p;p 0;// 先换0for(int i 0; i s; i){if(0 nums[i])swap(nums[p], nums[i]);}// 再换1for(int i p; i s; i){if(1 nums[i])swap(nums[p], nums[i]);}return;}
};
