给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
- 输入: [1,1,2]
- 输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
这道题的关键在给定的序列可以包含重复的数字,不注意这一点可能会求得大量重复的全排列:重复数字填入顺序不同得到的排列是相同的全排列,不是不同的全排列。
eg:上面示例中有两个1,一个2,为了区分两个1 我们记作输入[1(1), 1(2), 2]
排列 [1(1), 1(2), 2]和排列[1(2), 1(1), 2]实际上是相同的排列
为了区分这类重复的全排列,我们固定重复数字的填入顺序:
- 首先对输入序列排序,使相同的数字在序列中连续
- 固定重复数字的填入顺序,即1(1)在所有1中一定是最先填入全排列中的数字,1(2)一定是所有1中第二排入全排列中的数字,依次类推...
- 要想达到这一点:我们首先用一个数组visit[]表示第i个位置的数字是否填入了全排列中,其次设定条件,只有当重复数字的前一个数字填入了排列中,这个数字才可以填入全排列。假定当前判断是否要填入的数字为nums[i],只有当
visit[i-1]==true && nums[i] == nums[i-1]
时,重复数字才可以填入,也就是下面代码中visit[i-1]==false && nums[i] == nums[i-1]
时,跳过当前重复数字nums[i],不允许填入
下面给出代码:
class Solution {
private:
vector<bool> visit;
vector<vector<int> > ans;
public:
/**
给定一个可包含重复数字的序列,返回所有不重复的全排列
**/
vector<vector<int>> permuteUnique(vector<int>& nums) {
visit.resize(nums.size());
sort(nums.begin(), nums.end());
vector<int> tmp;
getNextNum(nums, tmp, 0);
return ans;
}
/**
index 表示将要填的位置 从0~size-1的位置
**/
void getNextNum(vector<int>& nums, vector<int>& temp, int index){
if (index == nums.size()) {// 填完了所有位置,获得一个全排列
ans.push_back(temp);
// cout << "获得一个全排列" << endl;
return;
}
// index < n 还需要向当前index位置填入一个数字
for (int i = 0; i < nums.size(); ++i) {
// 如果nums[i] 填过了 或者 nums[i]不是当前连续重复数字的第一个位置
if (visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1] )) {
continue;
}
// 填入当前nums[i]
// cout << "填入数字" << nums[i] << endl;
visit[i] = true;
temp.push_back(nums[i]);
// 获取下一个位置的数字
getNextNum(nums, temp, index+1);
temp.pop_back();
visit[i] = false;
}
}
};
Comments | 0 条评论