permutation i and ii

Jaden 发布于2019-08-14 17:18 / 1239人阅读

摘要：最直观的方法就是插入法，可以在头，中间，尾每个有空隙的地方插入元素。基本操作是该操作时间复杂度是因为以后的元素要移位。基于位置，时间复杂度是所以我们选择时间复杂度小的。比较的是两个长度为的数组，比较的是两个元素。显然，选择长度短的。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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