Java 得到集合中所有子集

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 list = new ArrayList();

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> allsubsets = getSubsets(list);

for(ArrayList<Integer> subList : allsubsets) {

System.out.println(subList);

}

}

}

public static ArrayList> getSubsets(ArrayList subList) {

ArrayList> allsubsets = new ArrayList>();

int max = 1 << subList.size();

for(int loop = 0; loop < max; loop++) {

int index = 0;

int temp = loop;

ArrayList currentCharList = new ArrayList();

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。