[Leetcode]47. Permutations II(C++)

题目描述

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

例子

例子 1

Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]

例子 2

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints

1 <= nums.length <= 8

-10 <= nums[i] <= 10

解题思路

和 [Leetcode]46. Permutations(C++) 相比，这道题增加两个了条件：

数组有重复数字
在有重复数字的情况下输出的排列组合不能有重复的情况

我们以 LeetCode-46 的做法，分别解决这两个条件：

首先针对第一个条件，先考虑在有重复数字的情况怎么输出所有可能组合（暂时允许有重复情况，既 [1,1] 我们可以同时输出两个 [1,1]）

在上一题中我们的做法时用一个数组标记某个位置的元素有没有添加过，如果没有就添加，这个方法在这道题也是可行的（当然会会出现重复组合的情况下，比如针对 [1,1] 的情况，第一层循环中先添加第一个1然后再第二层循环中添加第二个1，同时在第一层循环中添加第二个1再在第一层循环中添加第一个1，这样就会输出两个 [1,1]）

除了用简单数组作为该位置的元素是否有出现过以外，我们还可以用哈希表来追踪每个元素出现过的次数，只要 nums[i] 次数不为 0 则说明剩余的 nums[i] 中还有未在当前排列中的，因此可以加入排列中。

下面解决第二个条件，题目要求不能出现重复排列，同样有两种思路：

可以用一个简单哈希表来追踪已经出现过的排列，若出现重复情况直接跳过即可。这种做法不会增加时间复杂度（哈希表的查询和插入为常数时间），但由于没有剪枝，同样不会降低时间复杂度。

此外，我们可以采取剪枝的做法来进行优化。首先对数组进行排列，然后在每一层遍历中（假设为第 i 层），此时我们遍历数组准备为当前组合添加第 i 个元素。在遍历过程中，假如 nums[j] == nums[j - 1]，表示 nums[j] 作为第 i 个元素的情况下我们已经考虑过了，因此可以直接跳过。通过这样剪枝可以大幅减少时间复杂度。使用这种方法的话，我们必须采用计数哈希表来查询 nums[i] 的剩余个数。

代码如下：

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution {
public:
    std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
        std::vector<int> perm;
        std::vector<std::vector<int>> result;
        std::unordered_map<int, int> visited;

        for (auto&& num: nums) {
            visited[num]++;
        }

        std::sort(nums.begin(), nums.end());
        iterate(nums, perm, result, visited);
        return result;
    }

private:
    void iterate(const std::vector<int>& nums, std::vector<int>& perm, std::vector<std::vector<int>>& result, std::unordered_map<int, int>& visisted) {
        if (perm.size() == nums.size()) {
            result.push_back(perm);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            if (visisted[nums[i]] > 0) {
                perm.push_back(nums[i]);
                visisted[nums[i]]--;
                iterate(nums, perm, result, visisted);
                perm.pop_back();
                visisted[nums[i]]++;
            }
        }
    }
};

时间复杂度: O(2^n) – 由于有剪枝，实际时间复杂度会远小于这个值
空间复杂度: O(2^n)

GitHub 代码同步地址： 47.PermutationsIi.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions