1

我有一个多维日期数组，严格来说是一个ArrayList<ArrayList<Date>>. 我需要生成一个新的单维ArrayList<Date>，它由前面提到的多维数组的所有数组中的项组成。

我的第一个想法是将所有的arraylists连接在一起并对其进行排序，但是由于我不知道每个级别的元素数量，并且只需要生成的数组中的一定数量的元素，那会有点太多内存- 和处理器重。我的意思是，如果我将所有Date元素合并为一个ArrayList<Date>，我最终可能会得到一个包含数千个日期的数组列表......最终将其修剪为前 20 个。这就是我放弃该解决方案的原因。

那么，我可以使用哪种算法将 N（或 2）级别的元素排序为 1？

编辑

ArrayList<Date> a1 = new ArrayList<Date>();
a1.add(new Date(15));
a1.add(new Date(16));
a1.add(new Date(23));

ArrayList<Date> a2 = new ArrayList<Date>();
a2.add(new Date(1));
a2.add(new Date(25));
a2.add(new Date(89));

ArrayList<Date> a3 = new ArrayList<Date>();
a3.add(new Date(64));
a3.add(new Date(72));
a3.add(new Date(73));

ArrayList<ArrayList<Date>> b = new ArrayList<ArrayList<Date>>();
b.add(a1);
b.add(a2);
b.add(a3);

我需要实现一个getLatestDates(ArryList<ArrayList<Date>>, Integer)这样的方法来返回：

getLatestDates(b, 5) = {Date (89), Date(73), Date(72), Date(64), Date(25)};

在这个例子中只有 3 ArrayList，但在实践中我不知道这个数字，所以我认为移动设备的最佳解决方案不是加入所有二级数组列表并对新的大数组进行排序，如果只有一个要使用的项目数。

4

2 回答 2

2

根据您对问题的描述，我能想到的一些解决方案是：

  1. 当然，您建议的那个，即附加所有数组，然后对它们进行排序并取其中的前 20 个。
  2. 分别对这些内部数组中的每一个进行排序，然后从合并排序算法执行类似合并的过程，以合并所有这些内部数组中的前 20 个项目，并在合并所需数量的项目（例如 20 个项目）时退出合并循环。
  3. 对这些内部数组中的每一个进行排序，同时将日期放入其中。这样您就不必在后面逐一遍历。然后像上面所说的那样进行合并。

如果您在多个内部数组中有多个项目，并且您想要其中的前 20 个，那么您将不得不遍历内部数组以某种方式进行排序。这是我能想到的3个解决方案，欢迎其他人添加到我的帖子中。

编辑 ：

4.我能想到的另一种方法是：通过扫描整个内部数组数组来构建优先级队列（最小堆）。这将是一个深度受限的树，即因为您想要 20 个元素，所以树的最大深度可以是 4（假设根为 0）。堆中允许的最大项目数为 20。这种方法将在 O(log N) 时间内为您提供解决方案。当然，您将花费 O(N) 时间来扫描整个列表中的每个项目，并且构建该堆可能会占用额外的空间。

于 2013-06-28T10:06:41.027 回答
0

我会提出一个锦标赛算法。这可能非常复杂，但会给你一个与元素总数成线性关系的运行时间。

我将按如下方式进行：

  1. 每个列表都有一个锦标赛并存储锦标赛树（这棵树可能非常简单：每个元素，保存对手列表和结果）
  2. 在获胜者之间进行比赛并存储比赛树
  3. 第一个元素是锦标赛 2 的获胜者
  4. 第二个元素是锦标赛 1 或锦标赛 2 中获胜者的输家
  5. 第三个元素是锦标赛 1 或锦标赛 2 中 nr2 的失败者之一
  6. 等等...
于 2013-06-28T10:13:37.263 回答