首页 > 代码库 > leetcode. Permutations && Permutations II
leetcode. Permutations && Permutations II
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].
求全排列，根据Next Permutation , 已知某一排列情况下，可以求得下一排列，
因此现将数组排序，并依次求得下一排列，直到数组倒序为止。
1 vector<vector<int> > permute(vector<int> &num) 2 { 3 vector<vector<int> > ret; 4 vector<int> temp; 5 6 sort(num.begin(), num.end()); 7 for (int i = 0; i < num.size(); i++) 8 temp.push_back(num[i]); 9 10 ret.push_back(num);11 nextPermutation(num);12 while (!cmpvec(num, temp))13 {14 ret.push_back(num);15 nextPermutation(num);16 }17 18 return ret;19 }
bool cmpvec(vector<int> &num1, vector<int> &num2)
{
for (int i = 0; i < num1.size(); i++)
if (num1[i] != num2[i])
return false;
return true;
}
根据NextPermutation, 每次求得的序列都比当前序列大，不存在重复的情况。因此
上述代码完全满足Permutations II的要求。
leetcode. Permutations && Permutations II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。