[Leetcode] Permutations 全排列

scq000 發布于2019-08-14 12:31 / 1750人閱讀

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

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].

交換法 復雜度

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

思路

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

代碼

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){
        // 找到轉置完成后的解，將其存入列表中
        if(i == nums.length - 1){
            List list = new LinkedList();
            for(int j = 0; j < nums.length; j++){
                list.add(nums[j]);
            }
            res.add(list);
        }
        // 將當前位置的數跟后面的數交換，并搜索解
        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;
    }
}

深度優先搜索 復雜度

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

思路

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

代碼

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++){
                // 遇到已經加過的元素就跳過
                if(used[idx]){
                    continue;
                }
                // 加入該元素后繼續搜索
                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].

深度優先搜索 復雜度

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

思路

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

代碼

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++){
                // 遇到已經加過的元素就跳過
                if(used[idx]){
                    continue;
                }
                
                // 加入該元素后繼續搜索
                used[idx] = true;
                tmp.add(nums[idx]);
                helper(nums, tmp);
                tmp.remove(tmp.size()-1);
                used[idx] = false;
                // 跳過本輪的重復元素，確保每一輪只會加unique的數字
                while(idx < nums.length - 1 && nums[idx] == nums[idx + 1]){
                idx++;
            }
            }
        }
    }
}

GPU云服務器云服務器字符串全排列 java 全排列數列字符串全排列算法最快的全排列算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64532.html

leetcode 47 Permutations II

摘要：題目詳情題目要求輸入一個可能會有重復數字的數組，要求我們輸出可能組成的全排列無重復排列。可以用來實現，但這種實現方式復雜度高。另外一種實現思路是，新聲明一個數組來存儲中元素的使用狀況。以這個數組為例。題目詳情 Given a collection of numbers that might contain duplicates, return all possible unique ...

Cobub 2019-08-16 11:13 評論0 收藏0
[Leetcode] Permutation Sequence 全排列序列

摘要：找規律復雜度時間空間思路由于我們只要得到第個全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據全排列順序的性質，我們可以總結出一個規律假設全排列有個數組成，則第個全排列的第一位是。然后將得到，這個就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 評論0 收藏0
leetcode 46 Permutations

摘要：例如有如下的全排列想法這道題是用回溯法的思想解決的。回溯法在包含問題的所有解的解空間樹中，按照深度優先的策略，從根節點出發深度優先搜索，搜索到某個點的時候，先判斷該節點是否包含問題的解，如果包含就繼續探索，否則就逐層向根節點回溯。題目詳情 Given a collection of distinct numbers, return all possible permutations....

jubincn 2019-08-16 11:09 評論0 收藏0
leetcode47 Permutations II

摘要：當前的值如果已經被使用過，則繼續判斷下一個數值。則當第一個被添加進結果集時，可以繼續使用第二個作為元素添加進結果集從而生成。假設將表示為那么結果集中會確保永遠在數值的前面，從而避免了和的重復情況出現。題目要求 Given a collection of numbers that might contain duplicates, return all possible unique ...

taoszu 2019-08-14 18:33 評論0 收藏0
leetcode46 Permutation 排列組合

摘要：題目要求也就是得出所有可能的排列組合結果解題思路和代碼這題顯然采用遞歸的思路。在這里，我采用實現隊列，從隊列頭獲得上一組的結果，和當前元素結合之后，將結果插入到隊尾。題目要求 Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the ...

wendux 2019-08-16 10:34 評論0 收藏0