欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

九章算法 | 微软面试题:全排列

程序员文章站 2022-07-14 17:23:42
...

给定一个数字列表,返回其所有可能的排列。

在线评测地址:LintCode 领扣

样例 1:

输入:[1]
输出:
[
  [1]
] 

样例 2:

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

算法:DFS(回溯法)

算法分析

对于全排列,比如​[1,2,3]​的全排列,我们按顺序穷举,步骤如下: 1. 首先会固定第一位为 1,然后第二位如果取2,最后一位只能是3;再可以把第二位变成3,第三位就只能是2; 2. 接下来变化第一位变成 2,然后再像上述的过程穷举后两位分别是1,3; 3. 最后第一位是3,再穷举后两位分别是1,2,整个过程就完成了。

以上的过程,很适合使用DFS(回溯法)进行实现。

算法步骤

  1. 根据题目要求,首先需要定义并初始化一个布尔类型used数组记录每个数字是否已被使用,一个数组current记录当前遍历的排列,一个二维数组results记录所有结果;
  2. 对输入的数字列表nums进行深度优先搜索,传入的参数包括:数字列表nums、used、current、results;
  • 边界条件:当current中的元素个数和nums的相同,代表一次遍历完毕,将当前的current加入results并return;
  • 遍历nums,如果nums中当前这个元素未被使用,则在used中标记其已使用,将其加入current,并递归调用dfs;
  • 调用完毕后需要回退,即在used中标记其未使用;

复杂度分析

  • 时间复杂度:
    九章算法 | 微软面试题:全排列
  • 对于每一位,可以从n个元素中选择k个来放置,共有n位。
  • 空间复杂度:O(N!)
  • 共有N!个全排列,故需要保存N!个解
import java.util.ArrayList;import java.util.List;
public class Solution {
    /*
     * @param nums: A list of integers.
     * 
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();

        // 如果数组为空直接返回空
        if (nums == null) {
            return results;
        }

        //dfs
        dfs(nums, new boolean[nums.length], new ArrayList<Integer>(), results);

        return results;
    }

    private void dfs(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> results) {
        
        //找到一组排列,已到达边界条件
        if (nums.length == current.size()) {
            results.add(new ArrayList<Integer>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //i位置这个元素已经被用过
            if (used[i]) {
                continue;
            }

            //继续递归
            current.add(nums[i]);
            used[i] = true;
            dfs(nums, used, current, results);
            used[i] = false;
            current.remove(current.size() - 1);
        }
    }
}

更多题解参考:九章算法