O(n) 和 o(n) 是不同的意思，后者是前者的真子集。更不能写成 0(n)，最后这个东西只能被理解为零乘 n ，也就是 0 。 另外问题的表述不清楚：n 是什么？ 合理的表述如下：文件里有 n 个人的身高（厘米）且每个数据都是 整数.0 或者 整数.5 ，求最高的 1000 个人的身高。要求算法是 O(n) 时间的。 60 亿和 1000 都是常数，原来表述下的问题可以在 O(1) 时间内解决。
@geelaw 想起了去年找实习的面试，一道字符串相关的题，大意是给定一个字符串，找出其中第一个“只出现了一次的字符”的下标。我用 HashMap 做的，在已经明确字符串只包含英文字母的前提下，面试官非说最坏时间复杂度是 O(nlog n)，因为底层的红黑树最坏就是 O(n logn)…
用 hashtable, key 为身高, value 为该身高出现的次数 最后取出 hashtable 的 key, 按从大到小的顺序排序，再逐个看 value, 输出 key 的值直到 value 加起来 >= 1000 这样可行不？
