13
05/2015
[LeetCode] Permutations II
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(http://www.kangry.net/blog/?type=article&article_id=217)是姊妹题，唯一不同的是这道题的元素可以重复。其实我们在排列之前，先对整个数组进行排序。在递归过程中，若当前元素与前面一个元素相同，并且前面一个元素未被使用，表明当前排列已经出现过，我们不必继续递归下去。比如1,1,2,2。第一遍递归后，开始进行第二遍递归。在递归的第0层，发现第二个1与前面那个数相同，且前面那个1未被使用，那么我们就无需继续递归下去，第0层递归跳过第二个1，直接进入第三个数，即为2。代码如下，与Permutations代码即为相似，注释部分为不同的地方。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
int len = nums.size();
if(len==0){
return result;
}
std::sort(nums.begin(), nums.end()); //不同之处
bool isUse[len];
memset(isUse, 0, sizeof(bool)*len);
vector<int> item(len);
getPermutations(result, nums, isUse, item, 0);
return result;
}
void getPermutations(vector<vector<int>>& result, vector<int>& nums, bool* isUse, vector<int>& item, int itemLen){
if(itemLen==nums.size()){
result.push_back(item);
}else{
for(int i=0; i<nums.size(); i++){
if(i>0&&nums[i-1]==nums[i]&&!isUse[i-1]){ //添加一个判断条件
continue;
}
if(!isUse[i]){
isUse[i]=true;
item[itemLen] = nums[i];
getPermutations(result, nums, isUse, item, itemLen + 1);
isUse[i]=false;
}
}
}
}
};转载请注明：康瑞部落 » [LeetCode] Permutations II
0 条评论