如何在不连续的数据中计算出周、月、季的起止日期

Question

我有一系列的日期可以追溯到几年前，然而，它们不是连续的，这意味着在某些星期有7个日期，在另一些星期有3个日期，在一些极端情况下，那个星期只有一个日期。

我需要识别和标记每周的开始和结束日期，其中有可用的日期。例如，2015-06-23、2015-06-24、2015-06-25和2015-06-27是从2015-06-22 (Mon)开始的一周的记录，因此2015-06-23和2015-06-27应该分别是该周的开始和结束。如果给定的一周只记录了一个日期，那么该日期应该同时是该周的开始和结束。

将同样的概念扩展到月份，我需要识别和标记任何给定月份记录的开始和结束日期，而不管给定月份有多少个日期。

同样，这同样适用于四季的定义(根据开始和结束月份)可能是可定制的。也就是说，我可以将四季定义为:春季(3-5月)，夏季(6-8月)，秋季(9-11月)，冬季(12-2月)，或者我可以改变月份以使用一些不同的定义。事实上，我们可以完全抛弃传统的季节概念，只定义四个连续的周期，每个周期有三个连续的月。根据这样的定义，我需要确定每个给定时段/季节的开始日期和结束日期。

执行上述所有操作的高效算法是什么？

Answer 1

它是Element Distinctness Problem的一个变体，您需要找到每个"distinct“元素的2个特定实例。

(可以通过为i第th元素添加i / epsilon时间，然后找出是否存在具有多个日期的一周来减少元素的区分性)。

元素的清晰度通常通过以下两种方法之一来解决，也可以在这里应用：

1. 对数据进行排序，然后进行迭代。在排序的数据中，很容易在每个week/month/year/...
2. Populate中找到第一个和最后一个出现的日期，这是一个从周数字(整数)映射到一个列表的散列映射，包括本周的所有日期。找到第一个(最早的)数据很容易，然后您可以将这一周定义为“第一周”，然后，很容易计算从这个“第一周”开始的每个日期的偏移量(以周为单位)。因此，首先找到这个"week 1“日期(单次迭代)，然后创建所需的映射(在第二次迭代中，每次插入平均为O(1) )，最后-迭代映射并为每个日期输出列表中与本周相关的最小和最大日期。

请注意，如果您正在寻找可伸缩的解决方案，那么第二种方法可以很容易地转换为map-reduce。