leetcode-46-全排列

chenjx85

发布于 2018-08-30 17:20:52

6690

发布于 2018-08-30 17:20:52

文章被收录于专栏：chenjx85的技术专栏chenjx85的技术专栏

题目描述：

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

要完成的函数：

vector<vector<int>> permute(vector<int>& nums)

说明：

1、给定一个一维的vector，里面装着彼此不重复的int型整数，要求输出所有这些整数有可能组成的全排列。

每个全排列存储在一维的vector中，所有的全排列存储在二维的vector中，最后返回二维的vector。

2、这道题又是熟悉的树开枝散叶类的题目，这种题我们都是用递归做的。

在树的每个节点上，规律是一致的，用递归是最方便的做法。

举个例子，比如[1,2,3,4]，我们在第一个节点上，有4种选择，1/2/3/4，

如果选择了2，那么第二个节点上，有3种选择，1/3/4，

如果选择了4，那么第三个节点上，有2种选择，1/3。

但存在一个问题，我们怎么知道当前节点上的所有选择？我们要建一个“弹药库”吗，每次迭代一个进入循环？

但其实全排列就是元素之间的不断交换，我们可以利用这一点，降低时间复杂度。

代码如下：（附详解）

    void digui(vector<int>& nums,vector<vector<int>>& res,int left,int right,int* t)
    {
        if(left==right)//退出条件
        {
            res[*t]=nums;
            (*t)++;
            return;
        }
        for(int i=left;i<=right;i++)//当i==left时，其实没有交换，直接进入递归，当i！=left时，发生交换，进入递归
        {
            swap(nums[i],nums[left]);
            digui(nums,res,left+1,right,t);
            swap(nums[i],nums[left]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        int s1=nums.size(),result=s1,left=0,right=s1-1,count=0;//count表示当前是第几个全排列
        int *t=&count;//定义一个指针，指向count，便于后续处理
        for(int i=s1-1;i>1;i--)//result表示一共有多少个全排列
            result*=i;
        vector<vector<int>>res(result,nums);//提前申请好空间，避免多次申请空间造成的时间浪费
        digui(nums,res,left,right,t);//直接进入递归
        return res;//最终返回二维的vector
    }

还不是很清楚的同学，可以手推一下全过程，逻辑会清晰很多。

这道题我们不用自建“弹药库”，交换一下nums中的元素，nums就是我们的弹药库。

上述代码实测8ms，beats 100.00% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-08-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度