双指针解决数组排序问题

这个问题如果注意，用一句就可以解决

sort(nums.begin(),nums.end());

完事。但是人家明确说了，不能用代码库中的排序函数。我们就得自己去实现排序。其实这个问题很简单，因为里面只有三种颜色，用0 1 2 表示。思想也很简单，就是我们用双指针遍历数组。如果遇到0放在前面，遇到1就在那个位置，遇到2跳到最后。代码如下，个人感觉用双指针来解决数组的排序问题特别好使。

class Solution { public:void sortColors(vector<int>& nums) {int n=nums.size();int tmp=0,i=0;while(i<n){if(nums[i]==0)swap(nums[tmp++],nums[i++]);else if(nums[i]==1)i++;elseswap(nums[i],nums[--n]);}} };

合并区间也可以用双指针去解决一个指针用来指向当前元素，一个指针指向当前元素的下一个元素。

我们首先利用sort函数对数组进行排序，排序之后我们可以更方便的去比较。

 

这个题我们可以分情况讨论。首先最简单的情况就是不交叉比如[1,3][4,9]。即n[i][0]>c[i][1]

其中n代表下一个指针，c代表当前指针。这个时候直接将当前元素[1,3]直接保存即可无需再比较。只需要拿着[4,9]去和后边的比较。

第二种情况[4,9][5,8]前面的包含后边的。用代码表示即n[i][1]<=c[i][1]这个时候不用管[5，8]，因为[5.8]已经包含于[4,9],拿着[4,9]和后边的数继续进行比较。即n++,c不变。

最后一种情况，就是有重叠的情况，[4,9][7,10]这种只需零[4,9]中的9等于10即可用代码表示，c[i][1]=n[i][1]即可，n=++完事

贴代码

class Solution { public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.size() == 0 || intervals.size() == 1) return intervals;int u = 0, v = 0;vector<vector<int>> ans;// 思路①sort(intervals.begin(), intervals.end());// 思路②while (v < intervals.size()) { if (intervals[v][0] > intervals[u][1]) {ans.emplace_back(intervals[u]);u = v;} else if (intervals[v][1] <= intervals[u][1]) {v++;} else {intervals[u][1] = intervals[v][1];v++;}}//思路③ans.emplace_back(intervals[u]);return ans;} };

 

 

 

总结

以上是生活随笔为你收集整理的双指针解决数组排序问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。