一个易于理解的C++全排列(permutation)实现

通常我们用这两条语句可以得到一个数组的全排列:

sort(nums.begin(),nums.end());  //调用next_permutation求全排列的时候必须先给容器排序
do{
      get_pirnt(nums)  //这里是一个可以打印输出nums的函数
}while(next_permutation(nums.begin(),nums.end()); //调用该C++内置函数可以输出字典序大于当前nums的所有排列。

还可以自己写一个函数实现同样的功能,下面的函数使用递归,每次取出当前数组中的一个值,求出除掉它之后的数组的所有全排列,然后把它加到每一个全排列的开头。

class Solution {
public:
    vector<vector<int>> solution(vector<int>& nums)
    {   
        vector<vector<int>> res;
        vector<int> one;
        if(nums.size()==1) //如果数组只剩一个元素,则递归结束
        {
            one.push_back(nums[0]);
            res.push_back(one);
            return res;
        }
        
        for(int i=0;i<nums.size();i++) //每次从当前nums里取第i个数
        {
            vector<int> row(nums.begin(),nums.end());
            vector<int>::iterator index = row.begin()+i;
            row.erase(index);  //把第i个数从数组row里删除

            vector<vector<int>> current = solution(row); //把删除了第i个数之后的数组进行全排列,得到current
            for(int j=0;j<current.size();j++)
            {    //把current里的每一行数组的开头都加上nums[i]
                vector<int>::iterator it = current[j].begin();
                current[j].insert(it,nums[i]);
                res.push_back(current[j]);
            }
        }
        return res;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        return solution(nums);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏玄魂工作室

输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和...

25410
来自专栏Python小屋

Python内置函数sorted()和列表方法sort()排序规则不得不说的事

Python内置函数sorted()和列表方法sort()可以使用key参数指定排序规则,并且都是稳定排序,也就是说,对于指定规则不能涵盖的元素,本来谁在前面,...

27630
来自专栏小樱的经验随笔

51Nod 1277 字符串中的最大值(KMP,裸题)

1277 字符串中的最大值 题目来源: Codility 基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 一个字符串的前缀是...

29830
来自专栏天天

数据类型的转换

12330
来自专栏PHP实战技术

你应该这个姿势学习PHP(2)

2、is_array(),is_bool,is_int(),is_integer(),is_numeric(),is_string(),is_object(),...

40860
来自专栏CSDN技术头条

常见的七种排序算法解析

01 选择排序 实现原理 首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之...

20980
来自专栏lzj_learn_note

1-python基础

​ 同一个变量a可以反复赋值,且可以是不同类型的变量. 这种变量本身类型不固定的语言称为动态语言, 比如python, javascript....

27220
来自专栏PHP实战技术

你应该这个姿势学习PHP(2)

1、循环数组有哪几种方式 1)foreach(能够循环关联和索引数组以及对象) 2)for(只能循环索引数组) 3)list和each配合使用循环数组 $arr...

283100
来自专栏desperate633

LintCode 编辑距离题目分析代码

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

9920
来自专栏算法channel

Python|高阶函数

01 函数名也是变量! abs(-100) 对于abs()这个函数,完全可以把函数名abs看成变量,它指向一个计算绝对值的函数! 因此,函数名其实就是指向...

38760

扫码关注云+社区

领取腾讯云代金券