0

我安排了一堆活动，我想检查我安排的活动是否有 10 天的间隔，在这 10 天内没有活动发生。是否有良好的数据结构和搜索算法来找到 10 天的间隔？

4

3 回答 3

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 回答
0

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

编辑：认为我现在更好地理解了您的问题。两个选项：1）假设日期已排序，当它们中的两个之间的增量小于 10 时，对它们停止二进制搜索。也许您可以优先搜索具有较大日期范围的子数组。这介于 log n 和 n 之间。2）存储与上一个或下一个日期的差异与日期。使用优先级队列使它们按与上一个或下一个日期的差异进行排序。您可以在恒定时间中弹出具有最大差异的日期。

于 2013-02-27T16:44:51.113 回答
0

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

于 2013-02-27T17:17:24.843 回答