[LeetCode] java的排列与组合C(m,n)、A(m,n)

淩亂°似流年 2022-05-18 04:13 456阅读 0赞

# 考题 #

出处: [子集][Link 1]

> 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。  
> 说明：解集不能包含重复的子集。  
> `输入: nums = [1,2,3]`  
> `输出:[[3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]`

# 分析 #

首先 `过滤掉重复元素` ， 然后从 `0 ～ array.length` 之间找到所有组合即可。很容易会想到递归，但是网上找到了全排列的代码，到长一点的用例的时候出现了执行时间超限的问题，效率低，但是这种类型的场景和算法还是有必要记一下。后来从另一篇博客发现了用01组合来选取C(m,n)的方法，只要循环即可，不需要递归，性能也不错。

>  *  递归全排列 [Java实现排列A(m,n)][Java_A_m_n]

对于递归的关键代码：

/** * * @param prefix 拼接结果前缀 * @param total 需要从N个数中取total个数 * @param list 含有N个数的集合 */
        public void recursive(String prefix,int total, List<String> list) {
            //总的要循环多少次
            for(int i=0;i<list.size();i++){
                LinkedList<String> tempList = new LinkedList<String>(list);//复制一份list，不能对原list进行操作
                String remove = tempList.remove(i);//从集合中移出某个元素,防止出现重复数字
                String s = prefix+remove;//拼接结果
                if(total == 1){
       //当从N个数中取1个数时
                    System.out.println(s);//直接输出结果
                    sum++;
                }else{
                    int temp = total-1;//每到这里就得减一层
                    recursive(s, temp, tempList);//这里所传的值都是新值
                }
            }
        }

>  *  01方式的组合 [组合（从长度为n的字符串中取m个字符）—java两种实现方法][n_m_java]

01方式的关键思路

/** * * 具体思路：将我们的原始的字符串用01数组来代替，0表示没有，1表示有 * 例如：字符串：abcdefg;01数组:[1110000]->abc;[1010100]->ace * 长度为n的字符串，取m个字符 * 首先会初始化一个01数组，长度为n，前m数字为1，后面n-m个数字为0 * 然后扫描01数组，每一次发现10的时候，都给它变为01，同时将左边的1都移动到最左边，已经是最左边了就不移动， * 继续扫描直到所有的1都移动到了最右边 * 例如： * 1 1 1 0 0 * 1 1 0 1 0 * 1 0 1 1 0 * 0 1 1 1 0 * 1 1 0 0 1 * 1 0 1 0 1 * 0 1 1 0 1 * 1 0 0 1 1 * 0 1 0 1 1 * 0 0 1 1 1 * 纯算法时间效率：可能种类在4千万左右时间为1.2s左右 * @param input * @param strNum * @return */

# 针对该题的较优解法 #

// 解法 1
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
           List<List<Integer>> list1 = new ArrayList<List<Integer>>();  
            list1.add(new ArrayList<Integer>());
            for(int num:nums){
                int size=list1.size(); //必须定义在内循环前 
                for(int j=0;j<size;j++){
                    List<Integer> temp = new ArrayList<>(list1.get(j)); 
                    temp.add(num);
                    list1.add(temp);
                }
            }
            return list1;
        }
    }
    
    // 解法 2
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            boolean[] flags = new boolean[nums.length];
            List<List<Integer>> rst = new ArrayList<>();
            addSubsets(flags, 0, nums.length-1, nums, rst);
            return rst;
        }
        private void addSubsets(boolean[] flags, int start, int end, int[] nums, List<List<Integer>> rst){
            if(start == end){
                flags[start] = true;
                add(rst,flags,nums);
                flags[start] = false;
                add(rst,flags,nums);
            }else{
                flags[start] = true;
                addSubsets(flags,start+1,end,nums,rst);
                flags[start] = false;
                addSubsets(flags,start+1,end,nums,rst);
            }
        }
        private void add(List<List<Integer>> rst, boolean[] flags, int[] nums){
            List<Integer> one = new ArrayList<>();
            for(int i = 0;i<nums.length;++i){
                if(flags[i]){
                    one.add(nums[i]);
                }
            }
            rst.add(one);
        }
    }

[Link 1]: https://leetcode-cn.com/problems/subsets/description/
[Java_A_m_n]: https://blog.csdn.net/sky_100/article/details/775096168
[n_m_java]: https://blog.csdn.net/u014039577/article/details/50353198