首页 > 代码库 > LeetCode "Permutations"
LeetCode "Permutations"
Lexicographically algorithms:
1. Iterate array from back to front, and find the first decreasing point:
1,2,4,3 -- 4
2. Iterate array from back to front, again to find the first number larger than the previous number of the found one in #1:
1,2,4,3 -- 3
3. Swap the found two:
1,3,4,2
4. Reverse all elems from found index in #1 to the end:
1,3,2,4
class Solution {public: vector<vector<int> > permute(vector<int> &num) { std::sort(num.begin(), num.end()); vector<vector<int> > ret; ret.push_back(num); while(true) { vector<int> rlast = ret.back(); // Find decreasing item back->front int i; for(i = rlast.size() - 1; i > 0; i --) if(rlast[i] > rlast[i-1]) break; if(i == 0) break; int j = i - 1; int k; for( k = rlast.size() - 1; k > 0; k --) if(rlast[k] > rlast[j]) break; std::swap(rlast[j], rlast[k]); std::reverse(rlast.begin() + i, rlast.end()); ret.push_back(rlast); } return ret; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。