LeetCode 0047 - Permutations II
# Hints
STL
DFS
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
# 题意
给定一个长为 的数组(可能存在重复元素),求其所有本质不同的排列(即对结果进行去重)。
# 题解
用 STL 的 next_permutation
直接求解即可。该函数的内部实现包括了去重处理,不需要我们再进行额外的去重操作。代码和 LeetCode 0046 相同,此处就不再重复贴出了。
如果禁止使用这一标准库函数,我们可以 DFS 遍历全排列然后直接用 set 暴力去重,但是这样做的时间复杂度会很差。我们有必要先对数组排序,然后在 DFS 的过程中去重。
细节问题:
- 去重代码的位置和写法。
# AC代码(DFS)
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int> & nums) {
// 排序
sort(nums.begin(), nums.end());
// DFS
vector<bool> visited(nums.size(), false);
vector<int> perm(nums.size());
vector<vector<int>> res;
dfs(0, nums, visited, perm, res);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, vector<int> & nums, vector<bool> & visited, vector<int> & perm, vector<vector<int>> & res) {
// 递归终止
if (depth == nums.size()) {
res.push_back(perm);
return;
}
// 遍历
for (int i = 0; i < nums.size(); i ++) {
// 递归
if (!visited[i]) {
visited[i] = true;
perm[depth] = nums[i];
dfs(depth + 1, nums, visited, perm, s);
visited[i] = false;
// 去重
while (i < (int)nums.size() - 1 && nums[i] == nums[i + 1]) {
i ++;
}
}
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01