c - 在 O(n) 时间内对输入的字母进行排序

Question

我从一个 friend 的采访中听说了这个问题，我们都对如何找到解决方案感到困惑。他遇到了以下情况: 字符以未排序的顺序一个接一个地输入。在 O(n) 时间内按字母顺序(大写字母在前)输出这些字母。

所以输入的字母范围是'A' -> 'Z' 和 'a' -> 'z'。 显然，将字母移动到数组中并对其进行排序是行不通的(由于所需的时间复杂性)。 那么这将如何工作？阅读字母时，您有什么技巧吗？

Answer 1

trick就是分配一个大小为52的数组，统计每个字母出现的次数。然后只需从左到右扫描该数组，并多次打印每个字母。