Java应用程序花费大部分时间对一些键进行排序并删除重复项。
因此,选择一种适应的排序算法是强制性的。
键是整数(约256位,但不一定),数组大小在1000到100000键之间。
输入数组由连续的键组组成。这些组已经被排序,并且很小(大约10个键)。
数组示例(3组,32位键):
0x01000000
0x01010000
0x01010100
0x01010101
0x01000000
0x01010000
0x01010100
0x01010102
0x01000000
0x01020000
0x01020200
0x01020203在排序和删除重复项之后:
0x01000000
0x01010000
0x01010100
0x01010101
0x01010102
0x01020000
0x01020200
0x01020203有困难吗?知道吗?有联系吗?
谢谢
PS :在研究了排序算法之后,包括了合并排序、基排序、qui等的许多变体。我继续寻找哈希地图。
PPS :最后,我分了Java遗留合并排序,添加了过滤和排序组的概念。它提供了一个很好的加速。
发布于 2013-09-08 16:11:59
合并排序(排序)
由于您的输入数据是预先设定的,所以您可以先开始。您可以将每个列表中的第一个值输入到一个PriorityQueue中,取出最少的值,然后将该列表中的下一个值添加到队列中。重复一遍。带着一些最后的支票。:-)
我肯定会有更详细的答案。
更多的链接:
http://www.cs.washington.edu/education/courses/cse373/06sp/handouts/lecture08.pdf
而且,我自己的答案是非常完整的Java代码:
发布于 2013-09-08 16:13:11
没有更多细节的最简单的解决方案是
您应该能够将所有的行读入TreeSet并在末尾打印出来。
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
TreeSet<String> sortedSet = new TreeSet<String>();
for(String line; (line = br.readLine()) != null;)
sortedSet.add(line);
for (String s : sortedSet)
System.out.println(s);发布于 2013-09-08 16:11:21
我建议您在这里使用Collections.sort,因为这样可以处理重复项(如果您为数字创建一个集合),并且排序时间复杂度是O(nlogn),这是最好的。
如果您只有一组特定的数字,那么您可能需要看看基排序。
https://stackoverflow.com/questions/18685782
复制相似问题