大廠面試真題詳解：帶重複元素的排列

給出一個具有重複數字的清單，找出清單所有不同的排列。

線上評測位址：

領扣題庫官網 樣例 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