首页 > 代码库 > 【leetcode】Permutations
【leetcode】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]
.
分析:
permutations II 里的 一样,这里排个序就很简单,一样的代码提交,同能通过,看来,考察的应该不是如此简单。
这里给个不排序的吧,其实还是用的排序的原理,只是嫁接了一层。
实现:
vector<vector<int> > permute(vector<int> &num) { const int len = num.size(); vector<vector<int> > re; re.push_back(num); vector<int> index; if(len <= 1) return re; int i = len - 1; for (int n = 0; n < len; ++n) { index.push_back(n); } //reserve num, we don't plan to change it. vector<int> cp(num); while (1) { int ii = i; --i; if(i < 0 ) { return re; } if(index[ii] > index[i]){ int j = len - 1; while (index[j] < index[i]) --j; swap(index[i], index[j]); //you can write a reverse function yourself. //Reverse(num, ii, len - 1); reverse(index.begin() + ii,index.end()); for (int n = 0; n < len; ++n) { cp[n] = num[index[n]]; } re.push_back(cp); i = len - 1; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。