使用位陣列和位掩碼檢查時間範圍

Question

我有一個Java集合<String username, ArrayList loginTimes>。例如，一個條目可能看起來像["smith", [2012-10-2 08:04:23, 2012-10-4 06:34:21]]。時間有一秒鐘的決議。我正在尋找輸出所有用戶的用戶名列表，這些用戶在相隔24小時以上但相距不到7天的時間內至少登錄了兩次。

有一個簡單的爲O（n^2）的方式來做到這一點在那裏爲你每次登錄的時間比較所有其它的登錄時間給定用戶，並檢查它們是否匹配所需的條件。還有一些O（nlogn）方法，例如將loginTimes存儲爲二進制搜索樹，並且爲每個登錄時間（其中N個），查看樹（log N）以查看是否有另一個登錄時間符合要求。

我的理解是，還有一個解決方案（O（n）或更好？），您可以在登錄時創建一個位數組（BitSet），並使用某種掩碼來檢查所需條件至少兩次登錄時間相距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）