[Leetcode] Permutations 全排列

scq000 發(fā)布于2019-08-14 12:31 / 1744人閱讀

摘要：每一輪搜索選擇一個數(shù)加入列表中，同時我們還要維護一個全局的布爾數(shù)組，來標(biāo)記哪些元素已經(jīng)被加入列表了，這樣在下一輪搜索中要跳過這些元素。

Permutations I

Given a collection of numbers, return all possible permutations.
For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

交換法 復(fù)雜度

時間 O(N^2) 空間 O(N) 遞歸棧

思路

置換實際上是給出所有的排列方式，同樣是用深度優(yōu)先搜索，不過為了避免重復(fù)選擇的情況，我們要保證兩點：第一，所有數(shù)必須是數(shù)組中的，第二，數(shù)組中每個數(shù)只能用不多于也不少于一次。如果我們要多帶帶寫一個函數(shù)，來判斷下一輪搜索該選擇哪一個數(shù)就很麻煩了。這里有一個技巧，我們可以只將數(shù)兩兩交換，不過交換時只能跟自己后面的交換。

代碼

public class Solution {
    
    List> res;
    
    public List> permute(int[] nums) {
        res = new LinkedList>();
        helper(nums, 0);
        return res;
    }
    
    public void helper(int[] nums, int i){
        // 找到轉(zhuǎn)置完成后的解，將其存入列表中
        if(i == nums.length - 1){
            List list = new LinkedList();
            for(int j = 0; j < nums.length; j++){
                list.add(nums[j]);
            }
            res.add(list);
        }
        // 將當(dāng)前位置的數(shù)跟后面的數(shù)交換，并搜索解
        for(int j = i; j < nums.length; j++){
            swap(nums, i , j);
            helper(nums, i + 1);
            swap(nums, i, j);
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

深度優(yōu)先搜索 復(fù)雜度

時間 O(N) 空間 O(N) 遞歸棧

思路

我們還可以簡單的使用深度優(yōu)先搜索來解決這題。每一輪搜索選擇一個數(shù)加入列表中，同時我們還要維護一個全局的布爾數(shù)組，來標(biāo)記哪些元素已經(jīng)被加入列表了，這樣在下一輪搜索中要跳過這些元素。

代碼

public class Solution {
    
    List> res;
    boolean[] used;
    
    public List> permute(int[] nums) {
        res = new LinkedList>();
        used = new boolean[nums.length];
        List tmp = new LinkedList();
        helper(nums, tmp);
        return res;
    }
    
    private void helper(int[] nums, List tmp){
        if(tmp.size() == nums.length){
            List list = new LinkedList(tmp);
            res.add(list);
        } else {
            for(int idx = 0; idx < nums.length; idx++){
                // 遇到已經(jīng)加過的元素就跳過
                if(used[idx]){
                    continue;
                }
                // 加入該元素后繼續(xù)搜索
                used[idx] = true;
                tmp.add(nums[idx]);
                helper(nums, tmp);
                tmp.remove(tmp.size()-1);
                used[idx] = false;
            }
        }
    }
}

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

深度優(yōu)先搜索 復(fù)雜度

時間 O(N) 空間 O(N) 遞歸棧

思路

這題和上題的深度優(yōu)先搜索很相似，區(qū)別在于：1、要先將數(shù)組排序，確保重復(fù)的元素是在一起的。2、除了不能加入之前出現(xiàn)過的元素之外，還不能加入本輪搜索中出現(xiàn)過的元素。如何判斷哪些元素本輪出現(xiàn)過呢？我們加過一個數(shù)字并搜索后，在這一輪中把剩余的重復(fù)數(shù)字都跳過就行了，保證每一輪只有一個unique的數(shù)字出現(xiàn)。這和Combination Sum II中跳過重復(fù)元素的方法是一樣的，注意要判斷nums[i] == nums[i + 1]，因為for循環(huán)結(jié)束時i還會額外加1，我們要把i留在最后一個重復(fù)元素處。

代碼

public class Solution {
    
    List> res;
    boolean[] used;
    
    public List> permuteUnique(int[] nums) {
        res = new LinkedList>();
        used = new boolean[nums.length];
        Arrays.sort(nums);
        List tmp = new LinkedList();
        helper(nums, tmp);
        return res;
    }
    
    private void helper(int[] nums, List tmp){
        if(tmp.size() == nums.length){
            List list = new LinkedList(tmp);
            res.add(list);
        } else {
            for(int idx = 0; idx < nums.length; idx++){
                // 遇到已經(jīng)加過的元素就跳過
                if(used[idx]){
                    continue;
                }
                
                // 加入該元素后繼續(xù)搜索
                used[idx] = true;
                tmp.add(nums[idx]);
                helper(nums, tmp);
                tmp.remove(tmp.size()-1);
                used[idx] = false;
                // 跳過本輪的重復(fù)元素，確保每一輪只會加unique的數(shù)字
                while(idx < nums.length - 1 && nums[idx] == nums[idx + 1]){
                idx++;
            }
            }
        }
    }
}