题目

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].

分析

求给定向量数组所有元素的全排列问题。

我们知道n个元素有n!种全排列,而STL底层文件< algorithm >中有关于排列元素的标准算法:

  1. bool next_permutation(BidirectionalIterator beg , BidirectionalIterator end);

    该函数会改变区间[beg , end)内的元素次序,使它们符合“下一个排列次序”
  2. bool prev_permutation(BidirectionalIterator beg , BidirectionalIterator end);

    该函数会改变区间[beg , end)内的元素次序,使它们符合“上一个排列次序”

如果元素得以排列成(就字典顺序而言的)“正规”次序,则两个算法都返回true。所谓正规次序,对next_permutation()而言为升序,对prev_permutation()来说为降序。因此要走遍所有排列,必须将所有元素(按升序或者降序)排序,然后用循环方式调用next_permutation()或者prev_mutation()函数,直到算法返回false。

以上两个算法的复杂度是线性的,最多执行n/2次交换操作。

AC代码

class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ret; if (nums.empty())
return ret; sort(nums.begin(), nums.end());
ret.push_back(nums);
while (next_permutation(nums.begin(), nums.end()))
ret.push_back(nums); return ret;
}
};

GitHub测试程序源码

05-11 15:41