Java 得到集合中所有子集

面试中有一道笔试题,大概意思如下:

输入一个集合,输出这个集合的所有子集。例如输入:1,2,4  输出结果如下所示:

[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]

需要认识的:空集是任何集合的子集;真子集为不包含子集的集合;非空真子集即不包含子集与空集合

解题思路:

这道题可以使用“按位对应法”进行计算

如集合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中获取即可,具体修改详情如下图所示:

1. 在主函数打印的地方修改接受的返回值为HashSet类型

2. 在函数部分需要修改封装列表有list改为set

至此修改完成,测试运行结果如下所示:

分析代码可以得出它的时间复杂度是:O(n*log2n)

代码下载地址:

https://github.com/liang68/interview

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持我们!

(0)

相关推荐

  • Java 通过位运算求一个集合的所有子集方法

    Java没有自带的求一个集合的所有子集的方法,我们可以通过集合的子集规律来求. 一个集合的所有子集等于2^该集合的长度.比如{c,b,a}的长度为3,这个集合的子集就有8个. 这句话看起来很简单,但同时也隐含着高深的哲理.其实一个集合的所有集合,和2^该集合的长度这个数字有关.比如上面的例子,{c,b,a}的长度为3,则可以用0-7表示其所有子集.如下所示,改数字所对应的位置为1,则说明我需要这个数字形成子集.从0-7的二进制表示,刚好代表完,一个长度为3,子集个数为8的所有子集. 0(000)

  • java求解集合的子集的实例

     java求解集合的子集的实例 方式1:我们知道子集个数 2的n次方 比如a,b,c的子集 * 000  0  {}      *001  1   a      *010  2   b      *011  3   a,b (b,a)      *100  4   c      * 101  5   a,c (c,a)      * 110  6   b,c (c,b)      * 111  7   a,b,c 利用二进制的对应关系 @Test public void test1() thro

  • Java 得到集合中所有子集

    面试中有一道笔试题,大概意思如下: 输入一个集合,输出这个集合的所有子集.例如输入:1,2,4 输出结果如下所示: [1] [2] [4] [1, 2] [1, 4] [2, 4] [1, 2, 4] 需要认识的:空集是任何集合的子集:真子集为不包含子集的集合:非空真子集即不包含子集与空集合 解题思路: 这道题可以使用"按位对应法"进行计算 如集合A={a,b,c},对于任意一个元素,在每个子集中,要么存在,要么不存在. 映射为子集: (a,b,c) (1,1,1)->(a,b,

  • java ArrayList集合中的某个对象属性进行排序的实现代码

    开发中有时候需要自己封装分页排序时,List如何对某一属性排序呢,分享一个小实例,大家共勉,希望能对大家有用,请多多指教. 1.Student的Bean如下: public class Student { private int age; private String name; private String weight; public String getWeight() { return weight; } public void setWeight(String weight) { th

  • java去除集合中重复元素示例分享 java去除重复

    复制代码 代码如下: class ArrayListTest1 {    public static void main(String[] args) {        ArrayList al = new ArrayList();        al.add("java03");        al.add("java03");        al.add("java01");        al.add("java02")

  • java 如何实现正确的删除集合中的元素

    在java中如果我们需要遍历集合并删除其中的某些元素时,例如对于List来说,我们有三种办法. 1. 普通的for循环遍历并删除 public void forRemove(List<T> list, T obj){ for(int i = 0;i < list.size(); i++){ if (obj == list.get(i)) { list.remove(obj); } } } main中调用 <pre name="code" class="

  • Java函数式编程(四):在集合中查找元素

    查找元素 现在我们对这个设计优雅的转化集合的方法已经不陌生了,但它对查找元素却也是无能为力.不过filter方法却是为这个而生的. 我们现在要从一个名字列表中,取出那些以N开头的名字.当然可能一个也没有,结果可能是个空集合.我们先用老方法实现一把. 复制代码 代码如下: final List<String> startsWithN = new ArrayList<String>(); for(String name : friends) { if(name.startsWith(&

  • java中循环遍历删除List和Set集合中元素的方法(推荐)

    今天在做项目时,需要删除List和Set中的某些元素,当时使用边遍历,边删除的方法,却报了以下异常: ConcurrentModificationException 为了以后不忘记,使用烂笔头把它记录如下: 错误代码的写法,也就是报出上面异常的写法: Set<CheckWork> set = this.getUserDao().getAll(qf).get(0).getActionCheckWorks(); for(CheckWork checkWork : set){ if(checkWor

  • java的Map集合中按value值进行排序输出的实例代码

    java的Map集合中按value值进行排序输出的实例代码 import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.Set; public class Test { public static void main(String[] args) { Map<String ,Integer> map = new Has

  • Java 集合中的类关于线程安全

    Java集合中那些类是线程安全的 线程安全类 在集合框架中,有些类是线程安全的,这些都是jdk1.1中的出现的.在jdk1.2之后,就出现许许多多非线程安全的类. 下面是这些线程安全的同步的类: vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用.在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的. statck:堆栈类,先进后出 hashtable:就比hashmap多了个线程安全 enumeration:枚举,相当于迭代器

  • 用Java集合中的Collections.sort方法如何对list排序(两种方法)

    第一种是list中的对象实现Comparable接口,如下: /** * 根据order对User排序 */ public class User implements Comparable <user> { private String name; private Integer order; public String getName() { return name; } public void setName(String name) { this.name = name; } publi

随机推荐