【小白爬Leetcode47】全排列II PermunationsII

题目

Leetcode226 m e d i u m \color{#ff841c}{medium} medium
点击进入原题链接：全排列II PermunationsII

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

这道题的难点在于含有重复数字，所以要对答案数组进行去重，当然，为了效率起见，我们肯定不能用set对最后的结果进行去重，而应该在构建答案数组的时候就跳过重复的答案。这里列出了两种方法：哈希和回溯

方法一 哈希表+回溯

这是我做题的时候用的方法。先遍历一次数组，把每个数字出现的次数记录在哈希表里，在回溯搜索的时候，每用一次就把次数减少一下。

class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		if (nums.empty()) return ans;
		this->nums_size = nums.size();
		unordered_map<int, int> hash_list;
		for (int i = 0; i < nums.size(); ++i) {
			if (hash_list.find(nums[i]) == hash_list.end()) {
				hash_list[nums[i]] = 1;
			}
			else {
				hash_list[nums[i]]++;
			}
		}
		this->numbers = hash_list.size(); //一共有几个不重复的数字
		this->backTracking(hash_list, 0);
		return this->ans;
	}
private:
	int numbers = 0;
	int nums_size = 0;
	vector<vector<int>> ans; //结果数组
	vector<int> tmp;
	void backTracking(unordered_map<int, int> &hash_list, int pos) {
		if (pos == this->nums_size) {
			this->ans.emplace_back(this->tmp);
			return; //注意别忘了退出循环，不然就无限递归，*了！
		}
		for (auto &kv : hash_list) { //注意这个kv要是引用而不是拷贝
			if (kv.second > 0) {
				this->tmp.emplace_back(kv.first);
				kv.second--;
				backTracking(hash_list, pos + 1);
				//回溯
				this->tmp.pop_back();
				kv.second++;
			}
		}
	}
};

【时间复杂度】：O(n×n!)

1. 构建哈希表：设一共n个nums元素，构建哈希表的时间就是遍历nums数组并计算每个元素的HashCode，时间复杂度为O(n)；

2. 调用递归的次数，参考官方解答的说法：
   
   而每次调用递归的时候，通过哈希表获得当前数字的使用次数，是O(1)的（由于都是int数字做为键，不考虑hashCode冲突的情况），至于数组的尾插、尾删，哈希表的value自增、自减运算，都是O(1)的，因此调用O(n!)次数递归的时间复杂度就是O(n!)。

3. 把数组添加到结果数组里：
   所以叶子节点的时间复杂度为O(n×n!)
   综上，时间复杂度为O(n+n!+n×n!)=O(n×n!)
   空间复杂度：O(n)
   最坏情况下没有重复的数字，哈希表空间复杂度为O(n)。
   调用递归的时候栈的深度会达到n，每次递归也就用到常数空间，因此递归栈的空间复杂度为O(n)。
   综上空间复杂度为O(n+n) = O(2n) = O(n)。

方法二 排序+回溯

官方解答给出的方法。先将nums数组排序（升序降序无所谓），这样重复的数字会相邻排列，然后每次要选择相邻的重复数字时，都优先选择第一个没被选择的重复数组，比如：
[...6,6,6...]中6重复了3次，那么第一次要选择6的时候，我选择第0个6，即[...x,6,6...]，第二次要选择6的时候，我选择第1个6，即[...x,x,6...]，第三次要选择6的时候，我选择第2个6[...x,x,x...]。这个功能可以在循环中使用这一个判断语句来实现：

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    continue; //跳过非首位未选重复数字
}

这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。

class Solution {
    vector<int> vis;

public:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vis = vector<int>(nums.size(),0);
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

【时间复杂度】：O(n×n!)

1. 给数组排序的时间复杂度为O(nlogn)；

2. 调用递归的次数，参考官方解答的说法：
   
   而每次调用递归的时候，进行的操作都是常数级别的，因此调用O(n!)次数递归的时间复杂度就是O(n!)。

3. 把数组添加到结果数组里：
   所以叶子节点的时间复杂度为O(n×n!)
   综上，时间复杂度为O(nlogn+n!+n×n!)=O(n×n!)

空间复杂度：O(n)
需要O(n)的空间作为标记访问数组。
调用递归的时候栈的深度会达到n，每次递归也就用到常数空间，因此递归栈的空间复杂度为O(n)。
综上空间复杂度为O(n+n) = O(2n) = O(n)。