각 목록에 나타나는 모든 숫자 찾기

Question

HashMap에 저장된 Integer 객체의 ArrayList가 여러 개 있습니다.

각 목록에 나타나는 모든 숫자 (정수 개체)의 목록 (ArrayList)을 가져 오려고합니다.

내 생각은 지금까지입니다 :

1. 각 ArrayList를 통해 반복 처리와는 HashSet의
   • 이이 목록에있는 모든 값의 "목록"우리에게 줄 것이다에 모든 값을 추가하는 듯했으나 한번만의 반복과 함께 HashSet의
     2.1 내지
2. 반복 처리는 ArrayList.contains()
   수행 2.2 어떤 ArrayList도 false를 반환하지 않으면 최종 값이 모두 들어있는 "마스터 목록"에 숫자를 추가합니다.

더 빠르고 더 효율적으로 생각해 낼 수 있다면 재미있는 것은 내가 쓴 것처럼 합리적으로 좋은 해결책을 생각해 냈습니다. 하지만 다른 사람에게 유용하기 때문에 나는 여전히 게시 할 것입니다.

물론 더 나은 방법이 있다면 알려주세요.

Answer 1

1. 는 제 List에서 Set (예컨대 HashSet)을 만든다. 나머지 각 목록
2. : 작은 set.retainAll (list)list 둘 경우 set
   • 전화 충분히
   • 그렇지 않으면 2 단계의 두 번째 변형을 임계 값 set.retainAll (new HashSet <Integer> (list))

내가 말할 수없는 후 호출합니다. 더 빠르지 만, 아마도 > 20 크기 정도라고 생각합니다. 귀하의 목록이 모두 작 으면이 수표로 귀찮게하실 수 없습니다.

O (*) 부분뿐만 아니라 요소에 대해서도 신경을 쓰면 아파치 모음은 더 효율적인 정수 전용 구조를 가지고 있음을 기억합니다.

Answer 2

당신은 1 단계 변경해야합니다 : 를 - (이 짧은 목록에없는 경우 ... 그것은 모든 목록에없는)에 포함되어 다음 전화를 대신 HashSet에의

을 짧은 목록을 사용하여

public class TestLists { 

    private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>(); 

    private static List<Integer> filter(List<List<Integer>> listOfLists) { 

     // find the shortest list 
     List<Integer> shortestList = null; 
     for (List<Integer> list : listOfLists) { 
      if (shortestList == null || list.size() < shortestList.size()) { 
       shortestList = list; 
      } 
     } 

     // create result list from the shortest list 
     final List<Integer> result = new LinkedList<Integer>(shortestList); 

     // remove elements not present in all list from the result list 
     for (Integer valueToTest : shortestList) { 
      for (List<Integer> list : listOfLists) { 
       // no need to compare to itself 
       if (shortestList == list) { 
        continue; 
       } 

       // if one list doesn't contain value, remove from result and break loop 
       if (!list.contains(valueToTest)) { 
        result.remove(valueToTest); 
        break; 
       } 
      } 
     } 

     return result; 
    } 


    public static void main(String[] args) { 
     List<Integer> l1 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
     }}; 
     List<Integer> l2 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     List<Integer> l3 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     List<Integer> l4 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     List<Integer> l5 = new ArrayList<Integer>(){{ 
      add(100); 
      add(200); 
      add(300); 
     }}; 
     listOfLists.add(l1); 
     listOfLists.add(l2); 
     listOfLists.add(l3); 
     listOfLists.add(l4); 
     listOfLists.add(l5); 
     System.out.println(filter(listOfLists)); 

    } 

} 

,691,363 : 다른 목록 및

... 일부 코드를 하나 false를 반환하는 즉시 값을 제거 (이 값에 대한 추가 시험 생략) 짧은 목록에 답을 포함 끝에

을210

Answer 3

나는 당신의 목표를 이해하고 있는지 확신하지 못합니다.당신이 목록 < 정수> 개체의 컬렉션의 교차을 찾고자한다면, 당신은 다음과 같은 작업을 수행 할 수

public static List<Integer> intersection(Collection<List<Integer>> lists){ 
    if (lists.size()==0) 
     return Collections.emptyList(); 

    Iterator<List<Integer>> it = lists.iterator(); 
    HashSet<Integer> resSet = new HashSet<Integer>(it.next()); 
    while (it.hasNext()) 
     resSet.retainAll(new HashSet<Integer>(it.next())); 

    return new ArrayList<Integer>(resSet); 
} 

이 코드는 총 항목 수에 선형 시간에 실행됩니다. 사실 이것은 HashSet을 사용하기 때문에 평균 선형 시간입니다.

또한 루프에서 ArrayList.contains()를 사용하면이 메서드가 일정 시간에 실행되는 HashSet.contains()와 달리 선형 시간으로 실행되기 때문에 이차 복잡성이 발생할 수 있습니다.

Answer 4

Google 컬렉션 Multiset을 사용하면이 (표현형) 칵테일을 만듭니다 (비록 Eyal's answer도 좋지만). 다른 시간대와 비교해 볼 때 시간/기억력면에서는 효과가 없을 지 모르지만, 그 일은 매우 명확합니다. 목록을 가정

자체 내에 중복 포함하지 :

Multiset<Integer> counter = HashMultiset.create(); 
int totalLists = 0; 
// for each of your ArrayLists 
{ 
counter.addAll(list); 
totalLists++; 
} 

List<Integer> inAll = Lists.newArrayList(); 

for (Integer candidate : counter.elementSet()) 
    if (counter.count(candidate) == totalLists) inAll.add(candidate);` 

목록은 중복 요소를 포함 할 수있는 경우, 먼저 세트를 통해 전달 될 수 있습니다 : 마지막으로

counter.addAll(list) => counter.addAll(Sets.newHashSet(list)) 

, 이것은 또한 이상적입니다 원하는 경우 나중에 추가 데이터를 원할 수도 있습니다 (예 : 일부 특정 값이 얼마나 잘려나는지).

약간의 Eyal하자 (기본적으로 함께 집합을 통해 목록을 필터링하고 모든 중첩 요소들을 유지하는 단계를 접는) 수정하고 상기보다 경량화 다른 접근법 :

public List<Integer> intersection(Iterable<List<Integer>> lists) { 

Iterator<List<Integer>> listsIter = lists.iterator(); 
if (!listsIter.hasNext()) return Collections.emptyList(); 
Set<Integer> bag = new HashSet<Integer>(listsIter.next()); 
while (listsIter.hasNext() && !bag.isEmpty()) { 
    Iterator<Integer> itemIter = listsIter.next().iterator(); 
    Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size 
    Integer held; 
    while (itemIter.hasNext() && !bag.isEmpty()) 
    if (bag.remove(held = itemIter.next())) 
    holder.add(held); 
    bag = holder; 
} 
return new ArrayList<Integer>(bag); 
}