3

のJavaコレクションがあり<String username, ArrayList loginTimes>ます。たとえば、1 つのエントリは次のようになり["smith", [2012-10-2 08:04:23, 2012-10-4 06:34:21]]ます。時間の分解能は 1 秒です。24 時間以上間隔が 7 日未満の期間に少なくとも 2 回ログインしたすべてのユーザーのユーザー名のリストを出力しようとしています。

これを行うには、特定のユーザーの各ログイン時間を他のすべてのログイン時間と比較し、それらが必要な条件に一致するかどうかを確認する簡単な O(n^2) 方法があります。loginTimes をバイナリ検索ツリーとして保存し、各ログイン時間 (N 個) ごとにツリー (ログ N) を調べて、別のログイン時間があるかどうかを確認するなど、いくつかの O(nlogn) メソッドもあります。要件に一致します。

私の理解では、ログイン時間からビット配列 (BitSet) を作成し、何らかのマスクを使用して必要な条件 (少なくとも 2 回のログイン時間間隔は 24 時間で、間隔は 7 日未満です)。これを達成する方法を知っている人はいますか？または、他の可能な効率的な（O（n）以上の）ソリューションはありますか？

4

1 に答える 1

1

O（M * NlogN）で実行できます。ここで、Mはnoです。ユーザーの数（コレクションのサイズ）とNのloginTimesの平均の長さ（配列です）：


コレクション内のすべてのユーザーに対して、 次の
手順を実行します。1-リストloginTimesを並べ替えます。これはO（NlogN）タスクです
2-リストをスキャンして、制約が適用されるかどうかを検索します。これはO（N）時間で実行できます。

したがって、すべてのユーザーの合計コストはO（N）+ O（NlogN）=> O（2N * logN）=> O（NlogN）です。

于 2012-10-31T11:52:44.420 に答える