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을 추가해야 하며, 구체적인 수정 내용은 아래 그림과 같습니다.

1 . 허용된 반환 값을 기본 함수가

을 인쇄하는 HashSet 유형으로 수정합니다. 패키지 목록을 수정해야 하며 목록을 set로 변경

수정이 ​​완료되었으며, 테스트 실행 결과는 다음과 같습니다. 🎜>

얻을 수 있는 코드를 분석하면 시간복잡도는 O(n*log2n)

위 내용은 Java는 컬렉션의 모든 하위 집합에 대한 세부 정보를 얻습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!