个人主页界面网站,搬家,系统管理的主要内容,企业管理咨询机构题目已经提示可以一遍扫描了但是我还是没有想到#xff0c;其实双指针的想法我已经有了#xff0c;但是一想到有问题就觉得无法实现。这也揭示了我思维上的问题#xff1a;用一种方法解决问题遇到困难第一件事情不是想着如何攻克而是想着换一种方法。对自己的思维也不自信。…题目已经提示可以一遍扫描了但是我还是没有想到其实双指针的想法我已经有了但是一想到有问题就觉得无法实现。这也揭示了我思维上的问题用一种方法解决问题遇到困难第一件事情不是想着如何攻克而是想着换一种方法。对自己的思维也不自信。
我自己简单了写了一个两遍扫描的程序
class Solution {
public:vectorint cnt;void sortColors(vectorint nums) {cnt.resize(3,0);int n nums.size();for(int i0;in;i){cnt[nums[i]];}int idx 0;for(int i0;i3;i){for(int j0;jcnt[i];j){nums[idx] i;}}}
};仔细研究了一下题解题解给出了三种方法。第一种方法使用单指针需要遍历两次并没有什么借鉴意义。后面两种使用双指针的方法比较值得学习。
方法一
使用双指针p0p_0p0用来保存0和1的分界p1p_1p1用来1和2的分界刚开始的时候p0p_0p0和p1p_1p1都是0然后对整个数组进行扫描
如果是1先将当前元素和p1p_1p1指向的元素调换然后p1p_1p1如果是0先将当前元素和p1p_1p1指向的元素调换如果p1p_1p1在p0p_0p0的前面则说明需要将p1p_1p1所指向0和p0p_0p0指向的1进行交换。如果是2则不用处理
class Solution {
public:void sortColors(vectorint nums) {int n nums.size();int p00, p10;for(int i0;in;i){if(nums[i] 1){swap(nums[p1], nums[i]);} else if(nums[i] 0){swap(nums[p1], nums[i]);if(p1 p0){nums[p0] 0;nums[p1] 1;}p1; p0;}}}
};这种写法的核心在于让p1p_1p1作为分界点如果是1的话进行特殊处理
方法二
使用p0p_0p0保存0和1的分界点使用p2p_2p2保存1和2的分界点然后初始的时候让p0p_0p0为0p2p_2p2为n-1遍历数组
如果为0则将当前遍历元素和p0p_0p0所指向的元素进行交换并p0p_0p0如果为2则将当前遍历元素和p2p_2p2所指向的元素进行交换并−−p2--p_2−−p2。但是我们不能就这样遍历下一个元素因为我们不能确定交换以后当前指向元素是1所以我们要继续对当前元素进行处理如果为1不进行处理 当遍历到p2p_2p2的时候停止遍历
class Solution {
public:void sortColors(vectorint nums) {int n nums.size();int p0 0, p2 n-1;int idx 0;while(idx p2){if(nums[idx] 0){swap(nums[p0], nums[idx]);p0; idx;} else if(nums[idx] 2){swap(nums[p2], nums[idx]);--p2;} else{idx;}}}
};虽然这道题比较简单但是我觉得这道题的价值在于为快速排序的三路划分提供了一个比较好的方法对于快速排序的每一次划分我们可以把和枢纽相等的放在中间然后再分别处理小于枢纽的和大于枢纽的这样效率比较高。
