更新时间:2022-08-12 18:47:59
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]
.
无
/********************************* * 日期:2015-01-16 * 作者:SJF0115 * 题目: 46.Permutations * 网址:https://oj.leetcode.com/problems/permutations/ * 结果:AC * 来源:LeetCode * 博客: **********************************/ #include <iostream> #include <algorithm> #include <vector> using namespace std; class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > result; if(num.empty()){ return result; }//if vector<int> visited; // 递归 DFS(num,visited,result); return result; } private: void DFS(vector<int> &num,vector<int> &visited,vector<vector<int> > &result){ // 形成一个全排列 if(num.size() == visited.size()){ result.push_back(visited); return; }//if vector<int>::iterator isVisited; for(int i = 0;i < num.size();i++){ // 判断num[i]是否已经访问过 isVisited = find(visited.begin(),visited.end(),num[i]); // 如果没有访问过 if(isVisited == visited.end()){ visited.push_back(num[i]); DFS(num,visited,result); visited.pop_back(); }//if }//for } }; int main(){ Solution solution; vector<int> num; num.push_back(1); num.push_back(2); num.push_back(3); num.push_back(4); // 重新排列 vector<vector<int> > permutes = solution.permute(num); // 输出 for(int i = 0;i < permutes.size();i++){ cout<<"["; for(int j = 0;j < permutes[i].size();j++){ cout<<permutes[i][j]; }//for cout<<"]"<<endl; } return 0; }
直接调用STL中的next_permutation函数,如果在面试中面试官肯定会让你自己实现next_permutation函数
/********************************* * 日期:2015-01-17 * 作者:SJF0115 * 题目: 46.Permutations * 网址:https://oj.leetcode.com/problems/permutations/ * 结果:AC * 来源:LeetCode * 时间复杂度:O(n!) * 空间复杂度:O(1) * 博客: **********************************/ #include <iostream> #include <algorithm> #include <vector> using namespace std; class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > result; // 排序 sort(num.begin(),num.end()); // 直接调用STL中的next_permutation do{ result.push_back(num); }while(next_permutation(num.begin(),num.end())); return result; } }; int main(){ Solution solution; vector<int> num; num.push_back(1); num.push_back(2); num.push_back(3); num.push_back(4); // 重新排列 vector<vector<int> > permutes = solution.permute(num); // 输出 for(int i = 0;i < permutes.size();i++){ cout<<"["; for(int j = 0;j < permutes[i].size();j++){ cout<<permutes[i][j]; }//for cout<<"]"<<endl; } return 0; }
自己实现next_permutation函数
class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > result; // 排序 sort(num.begin(),num.end()); vector<int> tmp = num; // 全排列的下一排列 result.push_back(num); nextPermutation(num); while(num!= tmp){ result.push_back(num); nextPermutation(num); }//while return result; } private: void nextPermutation(vector<int> &num) { int count = num.size(); if(count == 0 || count == 1){ return; }//if // From right to left,find first digit which violate the increase // call it partitionNumber int index; for(index = count-2;index >= 0;index--){ if(num[index+1] > num[index]){ break; }//if }//for int tmp; // -1 indicate largest if(index != -1){ // From right to left,find first digit which large than partitionNumber // call it changeNumber for(int i = count-1;i > index;i--){ if(num[index] < num[i]){ // swap the partition index and changeNumber tmp = num[index]; num[index] = num[i]; num[i] = tmp; break; }//if }//for }//if // reverse all the digit on the right of partition index for(int i = index+1,j = count - 1;i < j;i++,j--){ tmp = num[i]; num[i] = num[j]; num[j] = tmp; }//for } };