permutation i and ii

Jaden 發布于2019-08-14 17:18 / 1242人閱讀

摘要：最直觀的方法就是插入法，可以在頭，中間，尾每個有空隙的地方插入元素?；静僮魇窃摬僮鲿r間復雜度是因為以后的元素要移位?；谖恢?，時間復雜度是所以我們選擇時間復雜度小的。比較的是兩個長度為的數組，比較的是兩個元素。顯然，選擇長度短的。

Given a collection of distinct numbers, return all possible permutations.
[1,2,3]
[  [1,2,3],   [1,3,2],   [2,1,3],   [2,3,1],   [3,1,2],   [3,2,1] ]

最直觀的方法就是插入法，可以在頭，中間，尾每個有空隙的地方插入元素。
基本操作是Arrays.add(num, pos), 該操作時間復雜度是O(n). 因為pos以后的元素要移位。最終結果的時間復雜度就是O(n*n!), n!個排列，沒個插入的時間復雜度是O(n).

另一種方法是swap?；谖恢?，swap(nums, i, j)時間復雜度是O(1). 所以我們選擇時間復雜度小的。

public class Solution {
    public List> permute(int[] nums) {
        // corner case, empty input
        List> res = new ArrayList>();
        permutating(nums, res, 0);
        return res;
    }
    
    public void permutating(int[] nums, List> res, int start){
        if(start == nums.length) {
            List list = new ArrayList();
            for(int n:nums){
                list.add(n);
            }
            res.add(list);
            return;
        }
        
        for(int i=start; i
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
如果輸入有重復怎么辦。
我們可以利用Set， 可以在輸出結果的時候比較是否有重復的結果。
我們也可以在每次swap的時候比較nums[i], nums[j]是否相同。
set比較的是兩個長度為O(n)的數組， swap比較的是兩個元素。顯然，選擇長度短的。
這里有兩個需要注意的地方，第一要先sort, 第二傳入的數組需要copy一個新的。這兩個步驟都是在避免，swap 的順序不同，可能產生相同的permutation. 
請手動[1,1,2,2]的每一步，就會發現重復的。
public class Solution {
    public List> permuteUnique(int[] nums) {
        List> res = new ArrayList>();
        if(nums == null) return null;
        Arrays.sort(nums);
        permutating(nums, res, 0);
        return res;
    }
    
    public void permutating(int[] nums, List> res, int start){
        if(start == nums.length) {
            List list = new ArrayList();
            for(int n:nums){
                list.add(n);
            }
            res.add(list);
            return;
        }
        // [1,1,2,2] different swap steps, may lead to same permutation
        for(int i=start; i
Generate all permutations in lexicographical order
i = 0  i = 1  i = 2    i=3(output)
abc -> abc -> abc  ->  abc
       acb <- return <- return
reverse(1,2) to abc
abc swap(0,1) to next greater bac

bac -> bac -> bac ->  bac
       bca  <- return
reverse(1,2) to bac
bac swap(0,2) to cab

cab -> ...
 
大致思路是找到第一個升續的組合，然后不斷從后向前產生下一個更大的組合。
import java.util.*;
import java.io.*;

public class Solution{

    public List permutation(String s){
        List res = new ArrayList();
        if(s == null || s.length() == 0) return res;
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        
        dfs(arr, 0, arr.length);
        return res;
    }
    
    public void dfs(char[] arr, int i, int n){
        if(i == n){
            StringBuilder sb = new StringBuilder();
            for(char c : arr){
                sb.append(c);
            }
            System.out.println(sb.toString());
            return;
        }
        
        for(int j = i; j < n; j++){
            dfs(arr, i+1, n);           // 在這里直接dfs走下去是用到recursion的方法。
            reverse(arr, i+1, n - 1);   // 為了還原到初始位置。
            
            int k = i+1;
            while(k < n && arr[i] > arr[k]){        // 找到下一個更大的字符.
                k++;
            }
            
            if(k >= n) continue;
            swap(arr, i, k);
        }
        
        reverse(arr, i + 1, n - 1);
    }
    
    public void swap(char[] arr, int i, int j){
        char t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    
    public void reverse(char[] arr, int i, int j){
        while(i < j){
            swap(arr, i++, j--);
        }
    }
    
    public static void main(String[] args){
        Solution sol = new Solution();
        String s = "abc";
        List res = sol.permutation(s);
        
        System.out.println(res.size());
    }
}

云服務器 GPU云服務器 Permutations Permutation And between and

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

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

【LC總結】回溯 (Subsets I II/Permutation I II/Combinatio

摘要：不同數包含重復數為的時候，表示在外層的循環正在被使用，所以當前循環遇到為一定要跳過。對當前循環要添加的數組，在添加當前元素后進行遞歸，遞歸之后要將當前元素的使用標記改為，表示已經使用和遞歸完畢，然后再將這個元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

tuomao 2019-08-14 15:53 評論0 收藏0
[LeetCode] Permutations I / II

Permutations I Problem Given a list of numbers, return all possible permutations. Example For nums = [1,2,3], the permutations are: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] Challe...

shery 2019-08-14 15:14 評論0 收藏0
[LintCode] Next Permutation II [Next Permutation]

摘要：從末位向前遍歷，假設循環開始全是倒序排列，如當第一次出現正序的時候，如的和此時從數列末尾向前循環到，找到第一個比大的交換這兩個數，變成倒置第位到末位的數為正序排列這里的是完全倒置的排列，如，即上面循環的情況完全沒有出現， Problem Implement next permutation, which rearranges numbers into the lexicographic...

mikasa 2019-08-14 15:15 評論0 收藏0
[Leetcode] Permutations 全排列

摘要：每一輪搜索選擇一個數加入列表中，同時我們還要維護一個全局的布爾數組，來標記哪些元素已經被加入列表了，這樣在下一輪搜索中要跳過這些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...

scq000 2019-08-14 12:31 評論0 收藏0
[Leetcode]PermutationsI II Next Permutation Permut

摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個排列，一種辦法是我們先求出所有的排序情況，但是題目規定不能占有額外空間。每次求出一個數字后，要及時的把它從中刪除掉。采用來構造結果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 評論0 收藏0