LeetCode 46. 全排列

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 46. 全排列

思路分析

回溯算法

参考代码

func permute(nums []int) [][]int {
	var res [][]int
	var path []int
	used := make([]bool, len(nums))

	var backtrack func()
	backtrack = func() {
		// 如果路径长度等于 nums 的长度，说明找到了一种排列
		if len(path) == len(nums) {
			temp := make([]int, len(path))
			copy(temp, path)
			res = append(res, temp)
			return
		}

		for i := 0; i < len(nums); i++ {
			if used[i] {
				continue // 如果当前元素已经被使用，跳过
			}

			path = append(path, nums[i]) // 选择当前元素
			used[i] = true               // 标记当前元素为已使用

			backtrack() // 递归调用

			used[i] = false           // 撤销选择
			path = path[:len(path)-1] // 撤销路径
		}
	}

	backtrack() // 开始回溯
	return res
}

时间复杂度： O (n!)，其中 n 是数组 nums 的长度。全排列的数量是 n!，我们需要生成所有的排列。 空间复杂度： O (n)，用于存储当前排列和结果集。

字典序算法是一种生成全排列的非递归方法。它通过不断生成下一个字典序排列来得到所有排列。具体步骤如下：

排序：首先将数组按升序排序，这样可以确保从字典序的第一个排列开始。

寻找逆序对：从右向左找到第一个逆序对，即找到第一个满足 nums[i] < nums[i+1] 的位置 i。

寻找交换位置：从右向左找到第一个大于 nums[i] 的位置 j，交换 nums[i] 和 nums[j]。

反转后缀：将 i 位置之后的所有元素反转，使其变为最小的字典序。

重复步骤 2-4：直到无法找到新的逆序对，即当前排列已经是字典序的最后一个排列。

func permute(nums []int) [][]int {
	// 首先将数组排序
	sort.Ints(nums)
	var res [][]int
	res = append(res, append([]int{}, nums...))

	for {
		// 从右向左找到第一个逆序对
		i := len(nums) - 2
		for i >= 0 && nums[i] >= nums[i+1] {
			i--
		}
		if i < 0 {
			break
		}

		// 从右向左找到第一个大于 nums[i] 的位置
		j := len(nums) - 1
		for nums[j] <= nums[i] {
			j--
		}

		// 交换 nums[i] 和 nums[j]
		nums[i], nums[j] = nums[j], nums[i]

		// 反转 i 位置之后的所有元素
		for l, r := i+1, len(nums)-1; l < r; {
			nums[l], nums[r] = nums[r], nums[l]
			l++
			r--
		}

		// 将新的排列添加到结果集中
		res = append(res, append([]int{}, nums...))
	}

	return res
}

时间复杂度：O (n * n!)，其中 n 是数组 nums 的长度。生成所有排列的时间复杂度为 O (n!)，每个排列需要 O (n) 的时间来复制到结果集中。 空间复杂度：O (n)，用于存储当前排列和结果集。

🍏 点击查看 Java 题解

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), res);
        return res;
    }

    public void backtrack(int[] nums, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int num : nums) {
            if (path.contains(num)) {
                continue;
            }
            path.add(num);
            backtrack(nums, path, res);
            path.remove(path.size() - 1);
        }
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/83334596