c++ - 如何用 O(n) 时间和 O(1) 空间对包含 n 个对象的组进行排序。每个对象有两个字段 : int and string.

Question

如何对具有 n 个对象的组进行排序。每个对象都有两个字段:int 和 string。

对象应根据 int 字段进行排序。但是，我们只知道 int 字段的范围而不是它的值。

它应该在 O(n) 时间和 O(1) 空间内完成。

我建议使用桶排序，但我不知道如何使用 O(1) 空间进行排序。

可以使用快速排序，但它是 O(n lg n)。

有什么想法吗？谢谢

Answer 1

一旦整数范围固定，范围内每个值的一个桶数组需要空间 O(1)。 Remember, any fixed, problem-instance-independent amount of space is O(1).

完整的解决方案假定对输出进行随机访问。

1. 我们首先计算每个输入整数的频率(O(n) 时间，O(1) 空间)
2. 根据频率，我们可以计算 O(1) 空间和时间中每个输入整数的第一个输出索引
3. 我们对输入进行第二次传递，并将每个输入项存储在正确排序的输出位置。存储一项后，我们增加该项的整数值的输出索引。 (O(n) 时间，O(1) 空间)

总的复杂度是 O(n) 时间，O(1) 空间，正如所宣传的那样。

当我们没有随机访问输出时，我没有看到满足要求的解决方案。