LeetCode(46)Permutations
2024-08-29 23:05:26
题目
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 >中有关于排列元素的标准算法:
bool next_permutation(BidirectionalIterator beg , BidirectionalIterator end);
该函数会改变区间[beg , end)内的元素次序,使它们符合“下一个排列次序”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;
}
};
最新文章
- 给缺少Python项目实战经验的人
- docker对数据卷进行还原操作
- PAT 1040. 有几个PAT(25)
- 【Go入门教程7】并发(goroutine,channels,Buffered Channels,Range和Close,Select,超时,runtime goroutine)
- Android -- 使用图库文件并可以裁剪文件(ImageView)
- HTML meta 标签用法(转)
- django自动化部署脚本
- 程序Bug---易错点
- ios编程之网络请求
- Nopcommerce 3.7 增加了Redis 作为缓存啦
- cocos2dx--cocos2dx3.1.1执行报无法解析的外部符号
- 【巧妙算法系列】【UVA 11384】 Help is needed for Dexter 正整数序列
- AMR音频编码器概述及文件格式分析
- 文件查找和比较命令 来自: http://man.linuxde.net/find
- Linux 系统下安装 rz/sz 命令及使用说明
- console.table(),在控制台以表格形式输出对象
- docker 容器 详解
- springmvc组件--ViewResolver
- macbook 下 spark开发环境搭建(基于idea 和maven)及spark单机写运行jar
- URL组成成分及各部分作用简介及urllib.parse / uri
热门文章
- mysql主从同步异常原因及恢复
- JEECMS9.3集成dubbo操作记录
- Android SQLite(2)如何判断表是否已经存在
- mysql 中 时间函数 now() current_timestamp() 和 sysdate() 比较
- [转]无废话SharePoint入门教程一[SharePoint概述]
- ADO.net增删改的使用
- [BZOJ1025][SCOI2009]游戏 DP+置换群
- P1583 魔法照片
- 460在全志r16平台tinav3.0系统下使用i2c-tools
- spring 整合struts