源码网商城,靠谱的源码在线交易网站 我的订单 购物车 帮助

源码网商城

Java 得到集合中所有子集

  • 时间:2020-06-03 10:59 编辑: 来源: 阅读:
  • 扫一扫,手机访问
摘要:Java 得到集合中所有子集
面试中有一道笔试题,大概意思如下: 输入一个集合,输出这个集合的所有子集。例如输入:1,2,4  输出结果如下所示: [1] [2] [4] [1, 2] [1, 4] [2, 4] [1, 2, 4] [b]需要认识的[/b]:空集是任何集合的子集;真子集为不包含子集的集合;非空真子集即不包含子集与空集合 [b]解题思路:[/b] 这道题可以使用“按位对应法”进行计算 如集合A={a,b,c},对于任意一个元素,在每个子集中,要么存在,要么不存在。 映射为子集: (a,b,c) (1,1,1)->(a,b,c) (1,1,0)->(a,b) (1,0,1)->(a,c) (1,0,0)->(a) (0,1,1)->(b,c) (0,1,0)->(b) (0,0,1)->(c) (0,0,0)->@(@表示空集) 观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数与集合映射...000 ~ 111...111(表示有,表示无,反之亦可),通过该整型数逐次增可遍历获取所有的数,即获取集合的相应子集。 主要考察的是位移运算以及逻辑思维能力,具体代码如下(经过本机真实认证,绝对可靠):
import java.util.ArrayList;
import java.util.Scanner;
import org.apache.commons.collections.CollectionUtils;
/**
 * 输入一个集合,输出这个集合的所有子集
 * @author liangyongxing
 * @time 2017-02-06
 */
public class SubListExport {
 public static void main(String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  System.out.println("请输入一串整数并在输入时用英文逗号隔开:");
  String inputString = new Scanner(System.in).next().toString();
  if (inputString != null && !inputString.isEmpty()) {
   String[] strArray = inputString.split(",");
   for (String str : strArray) {
    list.add(Integer.parseInt(str));
   }
   ArrayList<ArrayList<Integer>> allsubsets = getSubsets(list); 
   for(ArrayList<Integer> subList : allsubsets) {
    System.out.println(subList);
   }
  }
 }
 public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> subList) {
  ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>();
  int max = 1 << subList.size();
  for(int loop = 0; loop < max; loop++) {
   int index = 0;
   int temp = loop;
   ArrayList<Integer> currentCharList = new ArrayList<Integer>();
   while(temp > 0) {
    if((temp & 1) > 0) {
     currentCharList.add(subList.get(index));
    }
    temp>>=1;
    index++;
   }42    allsubsets.add(currentCharList);44   }
  return allsubsets;
 }
}
注:2017-02-08 10:01:32  上述代码有一定的漏洞即当输入有重复数字的时候,结果会有重复子集输出,并不能满足题目要求,需要在算出子集的时候加入HashSet进行排重,最终打印结果从sets中获取即可,具体修改详情如下图所示: [b]1. 在主函数打印的地方修改接受的返回值为HashSet类型[/b] [img]http://img.1sucai.cn/uploads/article/2018010710/20180107100137_0_58820.png[/img] [b]2. 在函数部分需要修改封装列表有list改为set[/b] [img]http://img.1sucai.cn/uploads/article/2018010710/20180107100137_1_18436.png[/img] 至此修改完成,测试运行结果如下所示: [img]http://img.1sucai.cn/uploads/article/2018010710/20180107100138_2_19587.png[/img] [b]分析代码可以得出它的时间复杂度是:O(n*log2n)[/b] [b]代码下载地址:[/b] [url=https://github.com/liang68/interview]https://github.com/liang68/interview[/url] 以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持编程素材网!
  • 全部评论(0)
联系客服
客服电话:
400-000-3129
微信版

扫一扫进微信版
返回顶部