1

对于这种排序情况，什么是好的（简单）算法/方法：

我有一个项目数组，其中每个项目由 2 个字段组成：（ID，时间戳）

有许多对具有相同 ID 的项目。

我想对数组进行排序，以使项目在 ID 之间尽可能地交替，从具有最早时间戳的项目开始。

例如，使用此输入：

(1, 15:00)
(1, 15:05)
(1, 15:10)
(2, 15:15)
(2, 15:20)
(2, 15:25)
(3, 15:30)
( 4, 15:35)
(3, 15:40)

我会得到这个输出：

(1, 15:00)
(2, 15:15)
(3, 15:30)
(4, 15:35)
(1, 15:05)
(2, 15:20)
(3, 15:40)
( 1, 15:10)
(2, 15:25)

我主要是在寻找一种概念上简单的算法，但如果它是高性能的当然很好。

现在我能想到的最好的是：

  1. 初始化/创建临时数组 T
  2. 从数组 A：获取具有最早时间戳的项目 X，其中 ID 不在 T 中
  3. 将 X 添加到结果集 R，将 X.ID 添加到 T，从 A 中弹出 X
  4. 只要 X 存在，重复步骤 2-3，否则从步骤 1 重新开始
  5. A为空时退出
4

1 回答 1

2
  1. 将所有项目放在一个排序的多图中，首先按 ID 排序，然后按时间排序。（例如，您可以使用您最喜欢的以 ID 为键的排序关联容器来实现这一点，其中排序容器中的每个值本身就是另一个包含所有时间值的排序容器。
  2. 虽然这个多重映射中仍然有任何元素：对于每个按升序排列的键，删除具有该键的第一个元素并将其添加到结果中。

完成后，如果我正确理解了问题，结果将按照您想要的顺序。

这是使用 Guava 的 Java 示例TreeMultimap（未经测试）：

TreeMultimap<Id, Timestamp> map = new TreeMultimap<Id, Timestamp>();
for (/* ... every item ... */) {
  map.put(item.getId(), item.getTimestamp());
}

List<Entry> outputList = new ArrayList<Entry>();
while (!map.isEmpty()) {
  for (Id key : map.keySet()) {
    Timestamp value = map.get(key).first();
    outputList.add(new Entry(key, value));
    map.remove(key, value);
  }
}
return outputList;
于 2013-02-13T22:19:45.877 回答