LeetCode Permutations II

LeetCode 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],
  [2,1,1]
]

这道题和之前的Permutations很像,只不过此时包含有重复元素。 在Permutations里,我使用了一个一个往里加的思路,今天我使用另一个思路。

为了得到一个序列的所有排列,可以采用每个元素和当前第一个元素交换的思路。比如要得到1,2,3的所有排列,第一轮每个元素和第一个元素交换得到

  • 1,2,3
  • 2,1,3
  • 3,2,1

此时每个元素都有打头的序列出现,再对每一个序列,除掉第一个元素,循环交换。比如对于1,2,3,此时把2,3作为一个新的序列,和此时的第一个元素2交换,得到序列:

  • 2,3
  • 3,2

然后再和之前的元素1拼接起来,得到以1开头的所有排列:

  • 1,2,3
  • 1,3,2

同理能得到以2,3打头的所有排列。用这种思路也可以求解Permutations这个题。当遇到有重复元素时,可以先对数组排序,在交换的时候,如果当前元素和前一个元素相同,则不再交换。最后再用set去重,完整代码如下:

class Solution {
public:
	void work(set<vector<int>>& ans, vector<int>& nums, int start) {
		if (start == nums.size()) {
			ans.insert(nums);
		}
		else {
			for (int i = start; i < nums.size(); i++) {
				if (i != start&&nums[i] == nums[i - 1])continue;
				swap(nums[i], nums[start]);
				work(ans, nums, start + 1);
				swap(nums[i], nums[start]);
			}
		}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		set<vector<int>> ans;
		work(ans, nums, 0);
		return vector<vector<int>>(ans.begin(),ans.end());
	}
};

本代码提交AC,用时48ms。速度比较慢,应该还有其他更优的算法。


新方法,使用和Permutations类似的dfs递归方法,只不过在递归的时候,判断一下,保证这次递归的元素不能和上一次相同。比如数组是[1,1,2],第一次从第一个1开始递归,那么在这层循环中,下一次递归就不能从第二个1开始了,但是下一层循环中还是应该可以选第二个1的。理解起来有点绕,假设我们把求[1,1,2]的全排列想象成从[1,1,2]中无放回的取数字,依先后顺序扔到3个格子中,每个格子只能放一个数字。那么第一次拿的数可能是1,1,2,则第一次拿第一个1和第二个1产生的全排列应该是完全一样的。

代码如下。第11行:用last记录本次循环中上一个递归的数,那么本次循环不再对同一个数递归了。因为先对数组排序了,所以所有相同的数字都会聚到一起,而且这样产生的全排列是按大小顺序排列的。

class Solution {
private:
	void dfs(const vector<int>& nums, vector<vector<int>>& ans, vector<int>& cand, vector<int> &visited) {
		if (cand.size() == nums.size()) {
			ans.push_back(cand);
			return;
		}
		int last = INT_MAX;
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
				if (i != 0 && nums[i] == last)continue; // 不能和上一次递归的元素相同,否则产生冗余排列
				cand.push_back(nums[i]);
				last = nums[i];
				visited[i] = 1;
				dfs(nums, ans, cand, visited);
				visited[i] = 0;
				cand.pop_back();
			}
		}
	}

public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		vector<int> cand, visited(nums.size(), 0);
		dfs(nums, ans, cand, visited);
		return ans;
	}
};

本代码提交AC,用时23MS,比前一种方法快,省掉了set去重。

二刷。上述解法固然正确,但是用INT_MAX来初始化last还是有风险的,万一数组中有INT_MAX呢。

更好的方法其实是,不用last记录上一次递归的值,二刷直接在内层if判断,如果i!=0且nums[i]==nums[i-1],说明这个数和上一个数相同,但是此时还不能continue,万一有[1,1,2]这种情况,在外层递归第二个1时,第一个1在上一轮是已经恢复了visited[0]=0的,所以这里可以加上一个visited[i-1]==0。完整代码如下:

class Solution {
private:
	void dfs(const vector<int>& nums, vector<vector<int>>& ans, vector<int>& cand, vector<int> &visited) {
		if (cand.size() == nums.size()) {
			ans.push_back(cand);
			return;
		}
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
                if(i != 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;
				cand.push_back(nums[i]);
				visited[i] = 1;
				dfs(nums, ans, cand, visited);
				visited[i] = 0;
				cand.pop_back();
			}
		}
	}

public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		vector<int> cand, visited(nums.size(), 0);
		dfs(nums, ans, cand, visited);
		return ans;
	}
};

本代码提交AC,用时23MS。

Leave a Reply

Your email address will not be published. Required fields are marked *