0

たくさんのイベントが予定されていますが、スケジュールされたイベントに 10 日間の間隔があり、その 10 日間でイベントが行われていないかどうかを確認したいと考えています。10日間隔を見つけるための適切なデータ構造と検索アルゴリズムはありますか?

4

3 に答える 3

0

効率やメモリ使用量などを気にするかどうかによって異なります。他のすべてが失敗した場合は、O（n * log（n））アルゴリズムを使用して日付で並べ替え、連続する日付のペアごとに差をとることができます。

編集：私はあなたの問題を今よく理解していると思います。2つのオプション：1）日付がソートされていると仮定すると、2つの間の増分が10未満になると、それらのバイナリ検索が停止します。おそらく、日付範囲が大きいサブ配列を優先的に検索できます。これは、lognとnの間のどこかにあります。2）前日または次の日付との差を日付とともに保存します。優先キューを使用して、前の日付または次の日付との差でソートされた状態に保ちます。一定時間で最大差のある日付をポップできます。

于 2013-02-27T16:44:51.113 に答える
0

リンクリストをソートしてスケジュールを保存し、日付をキーとして値をリンクリストノードアドレスのアドレスとしてハッシュマップに保存することもできます。したがって、スケジュールに 10 日間の時間があるかどうかを検索して確認するには、o(1) 時間、スケジュールを挿入するには、最大 o(n) 時間です。

于 2013-02-27T17:17:24.843 に答える
0

順序付きリンク リストを使用してイベントを保存し、イベントをハッシュ テーブル (キー: イベント日付) に保存します。これは、次のイベントよりも少なくとも 10 日早くなります。リンクされたリストに新しいイベントを挿入するときは、新しいイベントとその近隣の日付の違いを確認する必要があります。それまでにハッシュテーブルを変更します。

編集：

おそらく、追加のハッシュテーブルを作成する必要はありません。リスト項目が次のように見える特別な順序付きリンク リストを作成します。

[eventDate|nextEventPointer|next10DayEventPointer|previous10DayEventPointer]

next10DayEventPointer は、次のイベントより少なくとも 10 日早い次のイベントを指します。previous10DayEventPointer は、次のイベントより少なくとも 10 日前の前のイベントを指します。

HEAD アイテム next10DayEventPointer は、少なくとも次のイベントより前の最初のイベントを指します。HEAD アイテムの previous10DayEventPointer が NULL です。

next10DayEventPointer を使用して、HEAD から始まる 10 日間のイベントを照会できます。

挿入中に、必要に応じてポインターを更新する必要があります。

編集：

次のように二分探索を使用します。

class Program
{
    static void Main(string[] args)
    {
        Dictionary<int, int> result = new Dictionary<int, int>();
        int [] dates = {2, 2, 2, 2, 2, 7,18, 19, 23, 33, 34, 35, 50, 70};

        IsThereIntervalXBetween(dates, 10, 0, dates.Length - 1, result);
        foreach (var key in result.Keys)
            Console.WriteLine("Index:{0} Date:{1} Next:{2}",key,dates[key],dates[key+1]);
    }

    static void IsThereIntervalXBetween(int[] dates, int interval, int firstIndex, int lastIndex, Dictionary<int, int> result)
    {
        if (lastIndex - firstIndex == 1)
        {
            result.Add(firstIndex, dates[firstIndex]);
            return;
        }

        int middleIndex = (firstIndex + lastIndex) / 2;

        if (dates[middleIndex] - dates[firstIndex] >= interval)
            IsThereIntervalXBetween(dates, interval, firstIndex, middleIndex, result);


        if (dates[lastIndex] - dates[middleIndex] >= interval)
            IsThereIntervalXBetween(dates, interval, middleIndex, lastIndex, result);
    }
}

これは再帰的であり、好ましくありませんが、それでも非再帰に変換するのは簡単です。

于 2013-02-27T16:52:24.657 に答える