arrays - 给定一个包含 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) 时间。