LeetCode 46 全排列

这篇具有很好参考价值的文章主要介绍了LeetCode 46 全排列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

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

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

解法

回溯法

这个问题可以看作有 n 个排列成一行的空格,我们需要从左往右依此填入题目给定的 n 个数,每个数只能使用一次。那么很直接的可以想到一种穷举的算法,即从左往右每一个位置都依此尝试填入一个数,看能不能填完这 n 个空格,在程序中我们可以用「回溯法」来模拟这个过程。

定义回溯函数:

private void backtrack(int n, List<Integer> output, ArrayList<List<Integer>> res, int first) {
}

first为当前要填的位置,n位需要填的总位置数。

  • 如果 first=n,说明已经填完了 n 个位置(注意下标从 0 开始),找到了一个可行的解,将 output 放入答案数组中,递归结束。
  • 如果first < n,填第 first 个数的时候遍历题目给定的 n 个数,如果这个数没有被标记过,就尝试填入,并将其标记,继续尝试填下一个位置。
  • 假设我们已经填到第 first 个位置,那么 nums 数组中 [0,first−1]是已填过的数的集合,[first,n−1] 是待填的数的集合。

java代码:

class Solution {
    /**
     * 回溯
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();

        // nums不好交换位置,使用List
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        // 使用回溯
        backtrack(n, output, res, 0);
        return res;
    }

    /**
     * 回溯算法:
     *  如果 first=n,说明已经填完了 n 个位置(注意下标从 0 开始),找到了一个可行的解,将 output 放入答案数组中,递归结束。
     *  如果first < n,填第 first 个数的时候遍历题目给定的 n 个数,如果这个数没有被标记过,就尝试填入,并将其标记,继续尝试填下一个位置
     *  假设我们已经填到第 first 个位置,那么 nums 数组中 [0,first−1]是已填过的数的集合,[first,n−1] 是待填的数的集合
     *
     *
     * @param n  原数组长度,也是结果数组最后的总长度
     * @param output  当前的数组
     * @param res  结果数组
     * @param first  当前位置
     */
    private void backtrack(int n, List<Integer> output, ArrayList<List<Integer>> res, int first) {
        // 已经填完了 n 个位置,将 output 放入答案数组中,递归结束
        if (first == n) {
            // 注意这里的output,每次递归是公用的,所以需要把它放入新列表再放到结果列表
            res.add(new ArrayList<>(output));
        }

        // 开始填第first个数
        for (int i = first; i < n; i++) {
            // 动态维护数组,交换位置
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 回退,需要吧位置交换回来
            Collections.swap(output, first, i);
        }
    }
}

复杂度文章来源地址https://www.toymoban.com/news/detail-804005.html

  • 时间复杂度:O(n*n!),其中 n 为数组的长度
  • 空间复杂度:O(n)

到了这里,关于LeetCode 46 全排列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-中等题】46. 全排列

    1、子集去重版本 2、组合去重版本 3、子集非去重版本 这题中nums中的数各不相同,所以不需要去重: 而下面这题,nums中的数会存在重复值,就需要去重: 参考讲解视频:代码随想录—全排列不去重版本 关键在于递归之后还要还原做回溯动作: 所以最后,我们统计到的res才

    2024年02月09日
    浏览(48)
  • LeetCode46全排列(回溯入门)

    这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos 难度:中等 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案 示例 1 示例 2 示例 3 在很多刷题文章和书籍中,此题都被用做回溯算法的第一题,可见该题

    2024年02月10日
    浏览(35)
  • LeetCode.46. 全排列(回溯法入门)

    写在前面: 题目链接:LeetCode.46. 全排列 编程语言:C++ 题目难度:中等 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例2: 输入:nums = [0,1] 输出:

    2024年02月06日
    浏览(37)
  • LeetCode(力扣)46. 全排列Python

    https://leetcode.cn/problems/permutations/

    2024年02月09日
    浏览(31)
  • C++ | Leetcode C++题解之第46题全排列

    题目: 题解:

    2024年04月24日
    浏览(40)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(50)
  • 【算法与数据结构】474、LeetCode一和零

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题要找strs数组的最大子集,这个子集最多含有 m m m 个0和 n n n 个1。本题也可以抽象成一个01背包的问题。其中,strs内的元素就是物品,而 m m m 和 n n n 就是背包的维度。 d p [

    2024年01月22日
    浏览(40)
  • 【算法与数据结构】494、LeetCode目标和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题和这道题【算法与数据结构】1049、LeetCode 最后一块石头的重量 II类似,同样可以转换成01背包问题。下面开始论述。假设添加正号的整数子集和为 p o s i t i v e positive p os i t

    2024年01月20日
    浏览(41)
  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(65)
  • 【算法与数据结构】343、LeetCode整数拆分

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :博主做这道题的时候一直在思考,如何找到 k k k 个正整数, k k k 究竟为多少合适。从数学的逻辑上来说,将 n n n 均分为 k k k 个数之后, k k k 个数的乘积为最大(类似于相同周长

    2024年01月17日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包