비트 배열 및 비트 마스크로 시간 범위 확인

Question

Java 컬렉션 <String username, ArrayList loginTimes>이 있습니다. 예를 들어, 한 항목은 ["smith", [2012-10-2 08:04:23, 2012-10-4 06:34:21]]처럼 보일 수 있습니다. 시간에는 1 초의 해상도가 있습니다. 24 시간 이상 떨어져 있지만 7 일 미만 간격으로 적어도 두 번 로그인 한 모든 사용자의 사용자 이름 목록을 출력하려고합니다.

주어진 사용자의 경우 로그인 시간을 다른 모든 로그인 시간과 비교하여 필요한 조건과 일치하는지 확인하는 간단한 O (n^2) 방법이 있습니다. loginTimes를 이진 검색 트리로 저장하는 것과 같은 몇 가지 O (nlogn) 방법이 있으며 각 로그인 시간 (N 개)에 대해 트리 (로그 N)를보고 다른 로그인 시간이 있는지 확인합니다. 요구 사항을 충족시킵니다.

내 이해는 로그인 시간에서 비트 배열 (BitSet)을 만들고 (예 : 필요한 조건을 확인하기 위해 일종의 마스크를 사용하는) 솔루션 (O (n) 이상? 최소 두 번의 로그인 시간이 24 시간 떨어져 있지만 7 일 미만 간격). 아무도 이것이 어떻게 달성 될 수 있었는지 안다? 아니면 가능한 다른 효율적인 솔루션 (O (n) 또는 그 이상)?

Answer 1

O (M * NlogN)로 할 수 있습니다. 여기서 M은 아니오입니다. 사용자 (컬렉션의 크기)와 N loginTimes의 평균 길이 (이 배열의) :

컬렉션의 모든 사용자에 대해이 수행
1 종류의 목록 loginTimes. 이것은 O (NlogN) 작업입니다.
2 목록을 스캔하고 제약 조건이 적용되는지 검색하십시오. 이것은 O (N) 시간에 수행 할 수 있습니다.

따라서, 모든 사용자에 대한 총 비용은 O (N) + O (NlogN) => O (2N * logN) => O (NlogN)

은