sorting - 要在 O(n) 中排序的 N 个整数？

Question

假设您在 (0, n2 ) 范围内有 n 个整数。这些整数都是其他整数的平方根。指示是否可以在 O(n) 中对这些数字进行排序

我假设我们会对每个整数取平方根，但我不确定是否可以在 O(n) 中对它们进行排序，任何帮助将不胜感激

标签： sortingdata-structurestime-complexity

Answer 1

是的，如果您愿意使用 O(n) 空间：

• 您已将 N 个整数存储在数组 A 中。
• 分配具有 2n+1 位的位图 B，初始化为零。
• 对于每个整数，设置 B[A[i]] = 1
• 创建一个空列表：
• 按顺序迭代 B，以便如果 B[i] == 1 则将 i 添加到列表中。

它可以在 O(2n) == O(n) 的时间内完成。