leetcode46. 全排列(mid)

leetcode46. 全排列(mid)

全排列

• 题目描述
• 解题思路
• • 代码(排序 + 字典序 + 递归)
  • 复杂度
  • 代码(回溯)
  • 复杂度

力扣链接

题目描述

给定一个不含重复数字的数组 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 中的所有整数 互不相同

解题思路

官方题解链接

• 排序 + 字典序 + 递归
• 回溯

代码(排序 + 字典序 + 递归)

class Solution {
    public List> permute(int[] nums) {
        Arrays.sort(nums);
        List> list = new ArrayList<>();
        int n = nums.length - 1;
        recur(nums, list, n);
        return list;
    }

    void recur(int[] nums, List> list, int len) {
        //将初始值添加到数组中
        List temp = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            temp.add(nums[i]);
        }

        list.add(temp);
        int index1 = len - 1;

        while (index1 >= 0 && nums[index1] >= nums[index1 + 1]) {
            --index1;
        }

        //是否存在更大的排列 true: 存在 false: 不存在
        boolean flag = index1 != -1;
        if (!flag) {
            return;
        }


        int index2 = len;
        while (index2 >= 0 && nums[index2] <= nums[index1]) {
            --index2;
        }
        swap(nums, index1, index2);
        reverse(nums, index1 + 1, len);
        recur(nums, list, len);
    }

    void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            ++i;
            --j;
        }
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度

• 时间复杂度: 不会算
• 空间复杂度: O(n)

代码(回溯)

	public List> permute(int[] nums) {
        int n = nums.length;
        List> list = new ArrayList<>();
        List list2 = new ArrayList<>();
        for (int i : nums) {
            list2.add(i);
        }
        backtrace(nums, list, list2, 0, n);
        return list;
    }

    void backtrace(int[] nums, List> list, List list2, int first, int n) {
        if (first == n) {
        	// 所有数都填完了
            list.add(new ArrayList(list2));
        }

        for (int i = first; i < n; ++i) {
        	// 动态维护数组
            Collections.swap(list2, i, first);
            // 继续递归填下一个数
            backtrace(nums, list, list2, first + 1, n);
            // 撤销操作
            Collections.swap(list2, i, first);
        }
    }

复杂度