변수의 교차 수를 찾는 데 필요한 ArrayList의 개수가 다릅니다. 문자열의 수에 대한 현실적인 상한은 아마도 약 35이지만 더 많을 수 있습니다. 나는 어떤 코드도 필요 없으며, 무엇이 효율적 일 수 있는지에 대한 아이디어 만 가지고있다. 코딩을 시작하려하지만 다른 아이디어를 듣고 싶다는 구현이 있습니다.가변 개수의 문자열 집합을 효율적으로 찾을 수 있습니다.
현재 내 솔루션에 대해 생각해 보면 점심 시간이 Θ (n)이어야합니다.
도움 주셔서 감사합니다.
이
편집을 tshred : 명확히하기 위해, 나는 정말 그것을 할 수있는 빠른 방법이 알고 싶어요. Θ (n)보다 빠릅니다.
Set.retainAll()은 두 세트의 교차점을 찾는 방법입니다. HashSet을 사용하는 경우 ArrayList을 Set으로 변환하고 모두 retainAll()을 루프로 사용하면 모두 O (n)입니다.
이들을 정렬하고 (ng n) 이진 검색을 수행합니다 (lg n).
가장 좋은 방법은 HashSet을 사용하여 ArrayList 대신이 목록의 내용을 저장하는 것입니다. 그렇게 할 수 있다면 교차 할 요소를 추가 할 임시 HashSet을 만들 수 있습니다 (putAll (..) 메서드 사용). tempSet.retainAll (storedSet)과 tempSet은 교차를 포함합니다.
또 다른 아이디어 - 배열/세트가 다른 크기 인 경우 가장 작은 것으로 시작하는 것이 좋습니다.
단일 HashSet을 사용할 수 있습니다. add() 메소드는 객체가 alredy에있을 때 false를 반환합니다. 목록에서 객체를 추가하고 잘못된 반환 값의 개수를 표시하면 막대 그래프의 집합 + 데이터에 합집합이 생깁니다. 개수가 count + 1 인 객체는 교차로입니다. TreeSet에 카운트를 던지면 빈 교차점을 일찍 발견 할 수 있습니다.
또한 Google Guava에 정적 메서드 Sets.intersection(set1, set2)이있어 두 세트의 교집합을 수정할 수없는보기로 반환합니다.
허용되는 대답은 훌륭합니다. 업데이트로 : Java 8 이후 2 개의 Set의 교차 부분을 찾는 데 약간 더 효율적인 방법이 있습니다.
Set<String> intersection = set1.stream()
.filter(set2::contains)
.collect(Collectors.toSet());
이 약간 더 효율적입니다 그 이유는 원래의 접근 방식은 set1의 요소를 추가했기 때문에 그 다음 그들이 set2에없는 경우 다시 제거해야합니다. 이 접근법은 거기에 있어야 할 결과 세트 만 추가합니다.
엄밀히 말하면 Java 8 이전 버전을 사용할 수도 있지만 Stream이 없으면 코드가 상당히 힘들었을 것입니다.
두 세트의 크기가 상당히 다른 경우 작은 세트로 스트리밍하는 것이 좋습니다.
작은 노트 위로 스트리밍하지 않는 것이 좋습니다. 그것은 스트리밍 된 하나가 반복되는 반면, 다른 (더 큰) 세트는 [HashSet]에 대한 해쉬에 의해 검색됩니다. 이것은 [O (1)]입니다 (https://stackoverflow.com/questions/6574916/hashset- look-up-complexity)). –
도움을 주신 모든 분들께 감사드립니다. 문자열은 실제로 이미 존재하는 배열 목록에있는 객체 내부에 있으므로 배열에 남겨 두었습니다. 내가 언급 한 Java 콜렉션 클래스를 사용할 필요는 없지만 확실히 사용할 것입니다. 나는 권고에 감사한다. 문제가 해결되었습니다. – tshred