1
두 개의 정렬되지 않은 배열이 있고 각 배열의 길이는 n입니다. 이 배열에는 임의의 정수가 포함됩니다. 이 두 배열에 공통적 인 요소가있는 경우 찾을 방법은 Θ(n*logn)입니까?(알고리즘) 정렬되지 않은 배열 두 개가 정렬없이 Θ (n * logn) 시간에 공통적 인 요소가 있는지 찾습니다.
정렬 할 수 없습니다.
A
답변
0
및 B이 정렬되지 않은 배열, 길이 N 모두하자. @amit에서 제안한대로 해시 테이블을 사용할 수 있습니다. 그러나 더 빠른 알고리즘이 있습니다. 카드 (A) = 카드 (B)이므로 고속 교차 알고리즘은 Bloom filter을 사용하여 세트를 저장 한 다음 교차가 비트 AND 연산으로 구현됩니다. 여전히 O (n)이 필요하지만 상수 표기법에 숨겨진 상수 및 하위 항에 대해서는 더 나은 결과입니다.
+3
해시 테이블에는 O (N) 단계가 필요하며 그보다 더 잘할 수 없습니다. – wildplasser
+0
동일한 * O (n) * 상한을 달성하면서 점근 표기법 내에 숨겨진 상수 및 하위 조건에 관해서는 *를 더 잘 수행 할 수 있습니다. –
관련 문제
- 1. 고유하지 않은 C++ 정렬되지 않은 교차 알고리즘
- 2. O (logn) 시간에 작동하는 데이터 구조 설계
- 3. 두 배열에서 공통적 인 최대 요소를 찾으십니까?
- 4. Binarysearch 정렬되지 않은 배열
- 5. 알고리즘 - 정렬되지 않은 배열에서 삭제 시간 복잡도
- 6. n 개의 다른 배열에 공통적 인 최대 요소를 찾으십니까?
- 7. 두 배열에 공통적 인 것을 찾으십시오
- 8. O (n log n) 시간에 특수 점 k를 찾는 알고리즘
- 9. 정렬되지 않은 목록으로 배열 인쇄
- 10. 정렬되지 않은 인덱스로 배열 정렬
- 11. 정렬되지 않은 항목 집합이 있는지 확인하는 방법
- 12. 클래스에 배열 요소가 있는지 확인하십시오. 누르지 않은 것을 숨기기.
- 13. 노드의 평균 깊이가 Θ (lg n) 인 n- 노드 이진 탐색 트리의 높이에 점근선 상한값을 부여하십시오.
- 14. 정렬되지 않은 집합의 해시?
- 15. O (logn) 시간에 STL 힙을 사용하여 감소 키를 구현
- 16. 정렬되지 않은 배열에서 로그 시간으로 검색
- 17. 배열/목록에 요소가 있는지 여부를 확인해야합니까?
- 18. 알고리즘 - 빈 패킹, n 개의 객체를 포장하기위한 빈 배열
- 19. 배열 알고리즘
- 20. 정렬되지 않은 목록 Clearfix
- 21. 두 프로젝트간에 공통적 인 전역 변수를 처리하려면 어떻게해야합니까?
- 22. 배열 요소가 문자열에 있는지 확인하는 방법
- 23. D를 사용하여 배열 내부의 요소가 있는지 확인하십시오.
- 24. 배열 요소가 있는지 확인하는 방법은 무엇입니까?
- 25. 정렬되지 않은 배열에서 하나의 요소와 N 개의 요소를 찾음
- 26. 정렬되지 않은 배열의 상위 5 개 요소
- 27. 여러 파일에 공통적 인 행 찾기
- 28. 다수의 라디오 그룹에 공통적 인 청취자
- 29. n 차원 매칭 알고리즘
- 30. O (log n) 시간에 배열에서 중복 요소 찾기
먼저 시도해 보셨습니까? –
공간 제한이 있습니까? – Gumbo
O (n) 공간을 사용하면 한 배열의 모든 요소를 집합 (트리)에 삽입하고 다른 요소를 반복하면서 반복 할 수 있습니다 (트리가 정렬 된 데이터이므로 트리밍이므로 부정 행위입니다). 구조...). 트리 대신 해시 테이블을 사용하면'O (n)'의 평균 * 대소 문자를 구할 수 있습니다. – amit