等量项交替排序算法
等量项交替排序算法
提问于 2013-02-13 22:02:13
对于这种排序情况，什么是好的(简单的)算法/方法：
我有一个项目数组，其中每个项目由两个字段组成：(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)
我主要是在寻找一种概念上简单的算法，但如果它是性能良好的，那当然很好。
现在我能想到的最好的事情是：
- Init/创建临时数组T
- 从数组A:获取具有最早时间戳的条目X，其中ID不在T中
- 将X添加到结果集R，将X.ID添加到T，pop X从A添加
- 只要X存在，重复步骤2-3，否则在步骤1重新启动。
- A空时退出
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-02-13 22:19:45
- 将所有项目放入排序的multimap中，先按ID排序，然后按时间排序。(例如，您可以使用您最喜欢的按ID键的排序关联容器来实现这一点，其中排序容器中的每个值本身都是另一个保存所有时间值的排序容器。
- 尽管这个multimap中还有任何元素:对于每个按升序排列的键，使用该键删除第一个元素并将其添加到结果中。
当您完成时，如果我已经正确地理解了问题，结果将是您想要的顺序。
下面是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;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14864029
复制相关文章
相似问题
腾讯云开发者
