首页 > 代码库 > LeetCode： Permutations II 题解

LeetCode： Permutations II 题解

2024-07-08 15:02:45   228人阅读

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].
题解：依旧使用的是DFS的思想。

首先需要遍历输入数组，获取一共有多少种不同的数字，每个数字有多少个。 最简单的方法，排序后统计。

然后就是对应位置填数字的游戏了，DFS即可。

 1 class Solution { 2 public: 3    vector<vector<int> > vi; 4     vector<int> types;  // 数字缓存数组 5     vector<int> counts; // 数字计数器数组 6     vector<int> seq;    //  打印数组 7  8     void generatePermute(int len) 9     {10         if(len==0)11         {12             vi.push_back(seq);13             return;14         }15         for(int i=0;i<types.size();i++)16         {17             if((counts[i])>0)18             {19                 counts[i]--;20                 seq[len-1]=types[i];    //第len-1 是否存放types[i]21                 generatePermute(len-1);22                 counts[i]++;23             }24         }25     }26 27     vector< vector<int> > permuteUnique(vector<int> &num) {28         29         if(num.size()==0) return vi;30         sort(num.begin(),num.end());31         32         vi.clear();      //结果数组初始化33         types.clear();   //数字缓存数组初始化34         counts.clear();  //计数器初始化35         seq.resize(num.size());  //输出数组大小设定36 37         int j=0;38         types.push_back(num[0]);39         counts.push_back(1);40 41         for(int i=1;i<num.size();i++)42         {43             if(num[i]==types.back())44             {45                 counts.back()++;46             }47             else48             {49                 types.push_back(num[i]);50                 counts.push_back(1);51             }52         }53         generatePermute(num.size());54         return vi;55     }56 };

转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！


联系
我们