首页 > 代码库 > [LeetCode] Permutations II 排列

[LeetCode] 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].

 

Show Tags
 Backtracking
 
    这个就是输入一个数组,可能有重复,输出全部的排列。
    这题调用stl 就是如下了:
 1 #include <vector> 2 #include <iterator> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6  7 class Solution { 8 public: 9     vector<vector<int> > permuteUnique(vector<int> &num) {10         int n = num.size();11         vector<vector<int> >ret;12         if(n<1) return ret;13         if(n<2) {ret.push_back(num);    return ret; }14         sort(num.begin(),num.end());15         ret.push_back(num);16         while(next_permutation(num.begin(),num.end())){17             ret.push_back(num);18         }19         return ret;20     }21 };22 23 int main()24 {25     vector<int> num = {1,1,2};26     Solution sol;27     vector<vector<int> > ret = sol.permuteUnique(num);28     for(int i=0;i<ret.size();i++){29         copy(ret[i].begin(),ret[i].end(),ostream_iterator<int>(cout," "));30         cout<<endl;31     }32     return 0;33 }
View Code

    如果不调用嘛,就是自己写一个next_permutation,在Permutations 写过好多个版本了,回顾下stl 的实现逻辑吧:

  1. 输入数组a[],从右向左遍历,寻找相邻的两个数,使得 left<mid,没找到?就是没有,返回false了。
  2. 再次从右往左遍历,寻找right >left, 这次的right 不需要一定与left 相连,因为有1 这部,所以有保底的取值(mid)
  3. 交换left 与right。
  4. 逆向mid 与其右边。
  5. 结束。

 

 

 

 

 

[LeetCode] Permutations II 排列