首页 > 代码库 > 【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], and [2,1,1].

说明:

这个问题建议看下侯捷的《STL源码剖析》,这本书里有很多有用的函数实现,讲解的也算清楚。这里就不啰嗦了。不同的是,这里给出的数是会存在重复的,需要预先进行下排序,其实即使不存在重复,因为给定的num参数也未必是有序的,也总是要排序后从最小的开始,知道找到了最大的,那么next permutation就全部找完了。

实现:

//code 1
 bool nextPermutetion(vector<int> &num)
{
	int i = num.size() - 1;
	while (i >= 1)
	{
		if(num[i] > num[i - 1])
		{
			--i;
			int ii = num.size() - 1;
			while (ii > i && num[ii] <= num[i]) --ii;
			if(ii > i)
			{
				swap(num[i], num[ii]);
				reverse(num.begin() + i + 1, num.end());

				return true;
			}

		}
		else
			--i;
	}
	if(i == 0)
		return false;
	return true;
}

vector<vector<int> > permuteUnique(vector<int> &num) {
	vector<vector<int> > re;
	if(num.size() == 0)
		return re;
	sort(num.begin(), num.end());
	re.push_back(num);
	while (nextPermutetion(num))
	{
		re.push_back(num);
	}
	return re;
}
//code 2
vector<vector<int> > permuteUnique(vector<int> &num) {
	vector<vector<int> > re;
	if(num.size() == 0)
		return re;
	sort(num.begin(), num.end());
	re.push_back(num);
	int i = num.size() - 1;
	
	while(1){
	    int ii = i;
	    --i;
	    if(i < 0)
	    return re;
		if(num[ii] > num[i])
		{
			ii = num.size() - 1;
			while (ii > i && num[ii] <= num[i]) --ii;
			if(ii > i)
			{
				swap(num[i], num[ii]);
				reverse(num.begin() + i + 1, num.end());
				re.push_back(num);
				i = num.size() - 1;
			}
		}
	}//end while 1
	return re;
}