LeetCode:Permutations, Permutations II(二)
_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
};
算法3：
我们知道c++STL中有个函数next_permutation,这个函数时求某个排列的下一个大的排列。所谓的下一个大的排列可以如下解释：如果把数组元素看成是某个字符，这些字符组成一个字符串，下一个大的排列就是比当前排列代表的字符串更大（按字典序比较），且不存在介于两个字符串之间的字符串。例如对于字符串abc，它的下一个大排列是acb。
对于某个排列，我们如下求它的下一个大的排列：
从最尾端开始往前寻找两个相邻的元素，两者满足i < ii（令第一个元素为i，第二个元素为ii）
如果没有找到这样的一对元素则，表明当前的排列是最大的，没有下一个大的排列
如果找到，再从末尾开始找出第一个大于i的元素，记为j
交换元素i, j，再将ii后面的所有元素颠倒排列
按照的STL实现，如果某个排列没有比他大的下一个排列，调用这个函数还是会把原排列翻转，即得到最小的排列
有了这个函数后，这一题，我们先对数组按照升序排序，这样初始排列就是最小的，然后循环对数组求next_permutation，直到找不到下一个大的排列。
class Solution {
public:
vector > permuteUnique(vector &num) {
vector > res;
if(num.size() == 0)return res;
sort(num.begin(), num.end());
res.push_back(num);
while(mynext_permutation(num))res.push_back(num);
return res;
}
bool mynext_permutation(vector&num)
{
int n = num.size();
if(n <= 1)return false;
for(int i = n-2, ii = n-1; i >= 0; i--,ii--)
{
if(num[i] < num[ii])
{
int j = n-1;
while(num[j] <= num[i])j--;//从尾部找到第一个比num[i]大的数，一定可以找到
swap(num[i], num[j]);
reverse(num.begin()+ii, num.end());
}
}
reverse(num.begin(), num.end());
return false;
}
};
STL还有一个prev_permutation函数，求某个排列的上一个比他小的排列，方法和next_permutation相似：
对于某个排列，我们如下求它的上一个更小的排列：
从最尾端开始往前寻找两个相邻的元素，两者满足i > ii（令第一个元素为i，第二个元素为ii）
如果没有找到这样的一对元素则，表明当前的排列是最小的，没有下一个更小的排列
如果找到，再从末尾开始找出第一个小于i的元素，记为j
交换元素i, j，再将ii后面的所有元素颠倒排列
按照的STL实现，如果某个排列没有比他小的下一个排列，调用这个函数还是会把原排列翻转，即得到最大的排列
有了这个函数后，这一题，我们先对数组按照降序排序，这样初始排列就是最大的，然后循环对数组求prev_permutation，直到找不到下一个更小的排列。
class Solution {
public:
vector > permuteUnique(vector &num) {
vector > res;
if(num.size() == 0)return res;
sort(num.begin(), num.end(), greater());
res.push_back(num);
while(myprev_permutation(num))res.push_back(num);
return res;
}
bool myprev_permutation(vector&num)
{
int n = num.size();
if(n <= 1)return false;
for(int i = n-2, ii = n-1; i >= 0; i--,ii--)
{
if(num[i] > num[ii])
{
int j = n-1;
while(num[j] >= num[i])j--;//从尾部找到第一个比num[i]小的数，一定可以找到
swap(num[i], num[j]);
reverse(num.begin()+ii, num.end());
return true;
}
}
reverse(num.begin(), num.end());
return false;
}
};