Permutation II--LeetCode

痛定思痛。 2022-08-07 11:46 181阅读 0赞

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

思路：思路和前面一篇一样，只不过这里需要注意一点就是对于当前的这个字符，查看是否和以前都一样的，如果有一样的，这个就需要跳过

  1. #include <iostream> 
  2. #include <vector>
  3. using namespace std;
  5. /*
  6. 一个数组的排列 
  7. */
  8. bool isValid(vector<int>& vec,int begin,int index)
  9. {
  10.     int i;
  11.     for(i = begin;i<index;i++)
  12.     {
  13.         if(vec[i] == vec[index])
  14.             return false;
  15.     }
  16.     return true;
  17. }
  18. void Permutation(vector<int>& vec,int begin,int end) 
  19. {
  20.     int i=0;
  21.     if(begin >= end)
  22.     {
  24.         for(i=0;i<vec.size();i++)
  25.             cout<<vec[i]<<" ";
  26.         cout<<endl;
  27.         return ;
  28.     }
  29.     for(i=begin;i<=end;i++)
  30.     {
  31.         if(isValid(vec,begin,i))
  32.         {
  33.             swap(vec[begin],vec[i]);
  34.             Permutation(vec,begin+1,end);
  35.             swap(vec[begin],vec[i]);    
  36.         }
  38.     }    
  39. }
  41. int main()
  42. {
  43.     vector<int> vec(3);
  44.     int i;
  45.     for(i=0;i<vec.size();i++)
  46.         vec[i] = i+1;
  47.     vec[1] =1;
  48.     int pos =0;
  49.     Permutation(vec,pos,2);
  50.     return 0;
  51. }

发表评论

表情：
评论列表 （有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读