Permutations I & Permutations II

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

用DFS的方法,recursive不断寻找下一个数字,用一个boolean的数组visited来记录已经访问过的数字,避免重复。在访问结束的时候,只有满足条件sublist.size() 和 num.length 相等的情况下才能拷贝sublist并加入list中间。

我出现的问题: 由于对recursive的过程不够熟悉,所以在每次loop前拷贝了当前的sublist用在下一层中, 这样会大大增加space complexity,也是完全不必要的, 因为recursive不会同时执行两个loop,所以在某层recursive结束后我们只要删除加入的数字并且修改visited情况就可以保证sublist对下次loop使用的初始化是正确的。


public List<List<Integer>> permute(int[] num) {
        
        boolean[] visited = new boolean[num.length];
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        for(int i = 0 ; i < num.length; i ++)
            visited[i] = false;
            
        List<Integer> subList = new ArrayList<Integer>();
        generate(list,subList, num, visited);
        
        return list;
    }
    
    private void generate(List<List<Integer>> list, List<Integer> subList, int[] num, boolean[] visited){
        
        if(subList.size() == num.length){
            
            list.add(new ArrayList<Integer>(subList));
            return;
        }
        
        
        for(int i = 0; i < num.length; i ++){
        
            if(visited[i] == false){
                
                subList.add(num[i]);
                visited[i] = true;
                generate(list, subList, num, visited);
                visited[i] = false;
                subList.remove(subList.size()-1);
                
            }
        }
        
    }

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

和第一题类似,只是多了需要检验重复的情况。方法还是DFS,只是我们发现相同元素如果顺序的执行的话其实结果是重复的。

例如[1,1,2]
对第一个元素 先取 1, 剩下的选择就是 [1,2]
而如果从第二个元素开始 取 1, 剩下可以选择的仍然是[1,2]
这不是我们想要的情况,因此我们应该跳过连续选择相同元素的情况。

如何能保证我们不会选择同样地元素进行recursive处理呢? 我这里用的built in 的sort 方法,保证有相同元素它们就必然相邻,这样的话,当我们对不重样的第一个元素处理完发现后面是重复元素时,我们就跳过它。


public List<List<Integer>> permuteUnique(int[] num) {
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        ArrayList<Integer> number = new ArrayList<Integer>();
        boolean visited[] = new boolean[num.length];
        
        
        for(int i = 0; i < num.length; i ++)
            number.add(num[i]);
        
        Collections.sort(number);
        List<Integer> subList = new ArrayList<Integer>();
        generate(list, subList, number, visited);
        
        return list;
        
    }
    
    private void generate(List<List<Integer>> list, List<Integer> subList, ArrayList<Integer> number, boolean[] visited){
        
        if(subList.size() == number.size()){
            List<Integer> copyList = new ArrayList<Integer>(subList);
            list.add(copyList);
            return;
        }
        
        for(int i = 0; i < number.size(); i ++){
            
            if(visited[i] == false){
                
                subList.add(number.get(i));
                visited[i] = true;
                //recurse
                generate(list, subList, number, visited);
                
                visited[i] = false;
                subList.remove(subList.size()-1);
                while(i + 1 < number.size() && number.get(i) == number.get(i+1))
                    i ++;
            }
            
        }
    
    }

把自己有疑惑的问题和想法写出来,下次遇到避免重复一样的问题。

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s