大厂面试真题详解:带重复元素的排列

给出一个具有重复数字的列表,找出列表所有不同的排列。

在线评测地址:领扣题库官网

样例 1:

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

样例 2:

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

解题思路

  • 这道题我们需要使用dfs+回溯的方法来进行求解。
  • 我们定义dfs函数,使用递归的方法对决策树进行深度优先遍历。对于长度为n的数组nums,我们一位一位地生成它的排列数组,每深入一层数组长度就加1,遍历到叶节点时生成数组的长度达到n,即为我们的答案。
  • 由于数组中有重复元素,所以我们在遍历时需要剪枝操作。
    算法流程
  • 首先对数组进行排序,以使得重复元素相邻,这样才能进行剪枝。
  • 定义数组used,used[i]表示nums[i]是否已使用过,初始化全为false。数组path,表示从根结点到该节点经过的路径,即当前已生成的数组,初始化为空。数组res存储结果。
  • 使用dfs函数进行递归遍历

    • 递归出口:如果path的长度与nums的长度相等,说明已经生成好了排列数组path,那么我们把它的拷贝加入res中。
    • 遍历nums中的每个元素,对于nums[i]

      • 如果path中已经存在,即used[i]为true,跳过
      • 如果它和前一位元素相等,即nums[i-1] == nums[i],并且前一位元素已经搜索并回溯过了,即!used[i-1],为了避免生成重复的排列数组,也跳过
      • 排除上述两种情况后,把nums[i]变为true,然后对新生成的path继续送入dfs函数中。
      • 最后进行回溯操作,即删除path[i],used[i]变为false。
        举例说明
  • 如图所示,nums = [1, 2, 2],第二个2标记为2'用于区分相同元素。每个节点有path和used两个属性。
  • 首先,在根结点,path为[],used全为false(图中标为[0, 0, 0])。然后进行dfs遍历,到下一层,先加入元素1,path为[1],used为[1, 0,0 ]。再到下一层,由于1已经使用过了,我们加入元素2,path为[1, 2],used为[1, 1,0 ]。这样,每深一层path长度加1。达到最底层的叶节点,path为[1, 2, 2],把它加入res中。同理,可以得到其他的叶节点。
  • 注意,图中标出画叉的地方,代表出现了重复元素而进行剪枝。

大厂面试真题详解:带重复元素的排列

复杂度分析

  • 时间复杂度:O(n×n!),这里 n 为数组的长度。当没有重复元素时,排列数组有n!个,即最深层有n!个叶子节点,而拷贝操作需要n,所以时间复杂度为O(n×n!)
  • 空间复杂度:O(n×n!)。最差情况下,返回的全排列数组有n!个,每个长度为n。
    代码
public class Solution {
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Deque<Integer> path = new ArrayDeque<>(nums.length);
        // 排序
        Arrays.sort(nums);
        // dfs
        dfs(nums, used, path, res);
        return res;
    }
        private void dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        // 叶子节点
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        
        // 非叶节点
        for (int i = 0; i < nums.length; ++i) {
            // 元素已访问过 或者 是重复元素
            if ((used[i]) || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            
            // 在路径添加该节点,递归
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums, used, path, res);
            // 回溯
            used[i] = false;
            path.removeLast();
        }
    }
}

更多题解参考:九章官网solution

上一篇:【小Y学算法】⚡️每日LeetCode打卡⚡️——14.移除元素


下一篇:天池 × 九章算法 周赛第2场题解