找出这两个日期的差异

Question

我安排了一堆事件，我想检查我的计划事件中是否有10天的间隔，在这10天内没有事件发生。是否有好的数据结构和搜索算法来找到10天的间隔?

Answer 1

你可以用排序链表来存储时间表，也可以用日期作为键，值作为链表节点地址的哈希映射来存储时间表。因此，要搜索并查看您是否有10天的时间用于计划，其时间为o(1)，并插入计划的最大时间为o(n)。

Answer 2

取决于您是否关心效率，内存使用等。如果以上方法都失败了，您可以使用O(n*log(n))算法按日期排序，并取每对连续日期之间的差值。

编辑:我想我现在更了解你的问题了。两个选择:1)假设日期已经排序，当其中两个日期之间的增量为<10时，二分查找停止。也许您可以优先搜索具有较大日期范围的子数组。它介于log n和n之间。2)存储与前一日期或下一日期的差异。使用优先级队列将它们按照与前一个日期或下一个日期的差异进行排序。您可以在常数时间内弹出最大差异的日期

Answer 3

我将使用有序链表来存储事件，并且将事件存储在散列表(键:事件日期)中，该散列表至少比下一个早10天。当您向链表插入一个新事件时，您必须检查新事件与其相邻事件之间的日期差异。在此之前修改哈希表

编辑:

也许没有必要创建一个额外的哈希表。创建一个特殊的有序链表，其中列表项看起来像这样:

[eventDate | nextEventPointer | next10DayEventPointer | previous10DayEventPointer]

next10DayEventPointer指向下一个事件，该事件至少比下一个事件早10天。previous10DayEventPointer指向上一个事件，该事件至少比下一个事件早10天。

HEAD项目next10DayEventPointer指向至少早于下一个事件的第一个事件。头项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);
    }
}

这是递归的，这是不可取的，但仍然很容易转换为非递归的