두 개의 목록이 있습니다. 나는이 둘에서 가장 작은 공통 번호를 찾고 싶다. 중복을 허용하지 않기 때문에 HashSet 사용을 고려했습니다. 두 목록 요소를 모두 추가하는 동안 공통 번호를 찾을 수 있습니다. 그리고 HashSet은 단지 constant time을 삽입에 사용합니다. 이렇게하면 O(n)에서 2 개의 가장 작은 공통점을 찾을 수 있습니다. 하지만 constant time에 HashSet을 삽입하면 n 요소가 어떻게 삽입 될 수 있습니까? 이 경우 최후의 요소를 추가하려면, 최악의 경우는 버킷과 n 버킷을 비교할 필요가있는 올바른 버킷을 찾기 위해서 (때문에), O(n) 시간이 걸린다. 이 문제를 해결하고 미리 감사드립니다 ..!정수에 HashSet 사용
알고리즘은 매우 간단 보인다
HashSet 목록 A의 요소를 포함 구축합니다.min을 Integer.MAX_VALUE과 같이 큰 것으로 초기화하십시오.B의 각 요소에 대해 HashSet에 있는지 테스트합니다. 그럴 경우 min보다 작 으면 min을 업데이트하십시오.해싱 알고리즘은 해시 함수가 실제로 좋은 해시 함수라는 가정을 항상 유지하며 O (n) 최악의 경우에 대해 걱정하지 않아도됩니다.
도움 주셔서 감사합니다. 나는 더 이상 질문을해야만했다. 내 질문에 알고리즘을 작성했습니다. 하지만 내가 물어보고 싶은 것은 HashSet이 요소를 일정 시간에 삽입 할 수있는 방법이었습니다. – Panesar
버킷을 찾는 것은 일정 시간입니다. 이는 지정된 개체의 해시 값에만 의존하며 기존 개체에는 의존하지 않습니다.
고마워요. 나는이 방향으로 수색했다. 나는 버킷 아이디 (hashcode)에 대한 직접 주소 변환이이를위한 루트 솔루션이라고 가정한다. – Panesar
모든 알고리즘 책 (예 : Corman, Knuth)에서 답을 찾을 수 있습니다. 곧 : bucketIndex = toPositiveInteger (해시()) %의 buckets.length
이 숙제가 있습니까? –