给定1到1000之间1000万个整数的文件,我们如何在Java中按排序顺序打印它们？寻找一些有效的方法.

Question

整数总数= 1000万整数范围= 1 - 1000

因此,很明显整数不是唯一的.我们如何按排序顺序打印它们？我们应该使用位向量或ASCII阵列还是其他一些DS？做这个的最好方式是什么 ？

任何帮助将非常感谢!

Answer 1

最有效的方法是首先确定允许范围内的每个整数出现在数组中的次数.

int[] data = ...
int[] counts = new int[1000];
for (int i = 0; i < data.Length; i++)
    counts[data[i] - 1]++;

然后,您可以遍历counts数组并以正确的次数打印相应的整数.

for (int i = 0; i < counts.Length; i++)
{
    int count = counts[i];
    for (int j = 0; j < count; j++)
        Console.WriteLine(i + 1);
}

这个策略是O(n)时间.