Tag name:Permutation

[LeetCode] Permutations

01/21/2014 / No Comments

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-1个数的排列,然后在把第N个数插到每一个位置上去
有一点比较心烦的是,感觉代码还不够简洁,多占用了一点空间,每一次递归都申明了一个新的vector来存排列结果,有待改进
做这题也顺便复习了一遍容器iterator的用法,比如可以用*(vector.begin()+i)来代替vector[i],想获取最后一个数就可以*(vector.end()-1)
还有忘记之前在哪看到的了,说是判断容器是否为空最好用empty而不是size==0,因为在实现的时候,判断empty其实就是判断vector.begin()是否等于vector.end(),这样是比获取size要来得快的。

(突然意识到insert是很费时的操作,囧,感觉自己的解很渣,等学习一下别人的再搬过来吧。。。)