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<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)

#

以上是Java 得到集合中所有子集的詳細介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！