Permutations
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
求数组元素的全排列,数组不含重复元素
算法1:递归
类似于DFS的递归. 对于包含n个元素的数组,先确定第一位置的元素，第一个位置有n中可能(每次把后面的元素和第一个元素交换)，然后求子数组[2…n]的全排列。由于一个数列的总共有n！个排列，因此时间复杂度为O（n！）
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
if(num.size() == 0)return res;
vector<int> tmpres;
permuteRecur(num, 0, res, tmpres);
return res;
}
void permuteRecur(vector<int> &num, int index, vector<vector<int> >&res, vector<int>&tmpres)
{
if(index == num.size())
{
res.push_back(tmpres);
return;
}
for(int i = index; i < num.size(); i++)
{
swap(num[index], num[i]);
tmpres.push_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
};
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].
求数组元素的全排列,数组含重复元素
分析：要避免重复，就要保证我们枚举某个位置的元素时，不能枚举重复。
算法2：
在算法1的基础上，当我们枚举第i个位置的元素时，若要把后面第j个元素和i交换，则先要保证[i…j-1]范围内没有和位置j相同的元素。有以下两种做法（1）可以每次在需要交换时进行顺序查找；（2）用哈希表来查重。具体见下面的代码。
注意不要误以为以下两种做法能够去重：（1）最开始先对数组进行排序，以后每次交换时，只要保证当前要交换的元素和前一个元素不同，这种做法是错误的，虽然开始进行了排序，但是元素的交换会使数组再次变的无序（2）每次进入递归函数permuteRecur时，对从当前索引开始的子数组排序，这种做法也是错误的，因为每次交换元素后，我们要恢复交换的元素，如果在递归函数内排序，就不能正确的恢复交换的元素。
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
if(num.size() == 0)return res;
vector<int> tmpres;
permuteRecur(num, 0, res, tmpres);
return res;
}
void permuteRecur(vector<int> &num, int index, vector<vector<int> >&res, vector<int>&tmpres)
{
if(index == num.size())
{
res.push_back(tmpres);
return;
}
for(int i = index; i < num.size(); i++)
if(i == index || !find(num, index, i, num[i]))
{
swap(num[index], num[i]);
tmpres.push_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
//从数组的[start,end）范围内寻找元素target
bool find(vector<int> &num, int start, int end, int target)
{
for(int i = start; i < end; i++)
if(num[i] == target)
return true;
return false;
}
};
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
if(num.size() == 0)return res;
vector<int> tmpres;
permuteRecur(num, 0, res, tmpres);
return res;
}
void permuteRecur(vector<int> &num, int index, vector<vector<int> >&res, vector<int>&tmpres)
{
if(index == num.size())
{
res.push_back(tmpres);
return;
}
unordered_set<int> umap;
for(int i = index; i < num.size(); i++)
if(umap.find(num[i]) == umap.end())
{
umap.insert(num[i]);
swap(num[index], num[i]);
tmpres.push_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
};
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， vector
， return
， 第i个元素
， index
， 元素
， 查重软件
， num
， 查重
， 数据查重/去重
， 重复元素
， 数组全排列
， 重复数组元素
不重复排列
有重复元素的排列问题、带重复元素的排列、有重复元素的全排列、重复元素的排列问题、有重复元素的排列，以便于您获取更多的相关知识。