成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

permutation i and ii

Jaden / 1245人閱讀

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

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), 該操作時間復(fù)雜度是O(n). 因為pos以后的元素要移位。最終結(jié)果的時間復(fù)雜度就是O(n*n!), n!個排列，沒個插入的時間復(fù)雜度是O(n).

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

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.


如果輸入有重復(fù)怎么辦。
我們可以利用Set， 可以在輸出結(jié)果的時候比較是否有重復(fù)的結(jié)果。
我們也可以在每次swap的時候比較nums[i], nums[j]是否相同。
set比較的是兩個長度為O(n)的數(shù)組， swap比較的是兩個元素。顯然，選擇長度短的。


這里有兩個需要注意的地方，第一要先sort, 第二傳入的數(shù)組需要copy一個新的。這兩個步驟都是在避免，swap 的順序不同，可能產(chǎn)生相同的permutation. 
請手動[1,1,2,2]的每一步，就會發(fā)現(xiàn)重復(fù)的。


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 -> ...
 
大致思路是找到第一個升續(xù)的組合，然后不斷從后向前產(chǎn)生下一個更大的組合。


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());
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66547.html

相關(guān)文章

  • 【LC總結(jié)】回溯 (Subsets I II/Permutation I II/Combinatio

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

    tuomao 評論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 評論0 收藏0

  • [LintCode] Next Permutation II [Next Permutation]

    摘要：從末位向前遍歷，假設(shè)循環(huán)開始全是倒序排列，如當(dāng)?shù)谝淮纬霈F(xiàn)正序的時候，如的和此時從數(shù)列末尾向前循環(huán)到，找到第一個比大的交換這兩個數(shù)，變成倒置第位到末位的數(shù)為正序排列這里的是完全倒置的排列，如，即上面循環(huán)的情況完全沒有出現(xiàn)， Problem Implement next permutation, which rearranges numbers into the lexicographic...

    mikasa 評論0 收藏0

  • [Leetcode] Permutations 全排列

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

    scq000 評論0 收藏0

  • [Leetcode]PermutationsI II Next Permutation Permut

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

    ChristmasBoy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<