频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
LeetCode --- Permutations II
2015-03-03 14:57:50         来源:makuiyu的专栏  
收藏   我要投稿

题目链接:Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2] have the following unique permutations: 
[1,1,2], [1,2,1], and [2,1,1]. 

这道题的要求是给定一组数字,包含重复元素,生成所有的排列组合。

这道题是Permutations的基础上,允许数组中有重复元素。不过思路还是类似,只不过需要跳过重复元素。

世界杯投注官网

这是一个排列的问题,首先联想到的就是递归方式。对剩余元素排序,然后每次逐个固定每个没有重复元素到第一位置,然后递归排列剩下的元素。当固定到前面的元素数量等于数组长度的时候,递归终止。

注意一点,由于排序会造成num数组元素的顺序变化,因此调用两次swap(num[i], num[j])并不能恢复到原样,因此需要去掉递归函数参数num前面的引用符合‘&’,这样每次退出内层函数后,num数组的元素顺序回复原样。不过这样空间复杂度变高,时间复杂度变高了。。。

时间复杂度:O(n!)(结果数量)

空间复杂度:O(n!)

 1 class Solution
 2 {
 3 public:
 4     vector > permuteUnique(vector &num)
 5     {
 6         vector > vvi;
 7         permuteUnique(num, 0, vvi);
 8         return vvi;
 9     }
10 private:
11     void permuteUnique(vector num, int i, vector > &vvi)
12     {
13         if(i == num.size())
14         {
15             vvi.push_back(num);
16             return;
17         }
18         
19         sort(num.begin() + i, num.end());
20         
21         for(int j = i; j < num.size(); )
22         {
23             swap(num[i], num[j]);
24             permuteUnique(num, i + 1, vvi);
25             swap(num[i], num[j]);
26             
27             while(++ j < num.size() && num[j] == num[j - 1]);
28         }
29     }
30 };

2. next_permutation

由于next_permutation()函数在生成下一排列时候,会跳过重复情形,因此这道题和Permutations完全一样,利用next_permutation()函数,逐步生成下一个排列。由于next_permutation()在最后一个排列时返回false,因此可以先对数组排序,然后调用next_permutation()直到其返回false。

时间复杂度:O(n!)(结果数量)

空间复杂度:O(n!)

 1 class Solution
 2 {
 3 public:
 4     vector > permute(vector &num)
 5     {
 6         sort(num.begin(), num.end());
 7         
 8         vector > vvi({num});
 9         while(next_permutation(num.begin(), num.end()))
10             vvi.push_back(num);
11         
12         return vvi;
13     }
14 };

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:LeetCode --- Rotate Image
下一篇:CodeForces 520D Cubes
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑--致力于做实用的IT技术学习网站