“只要不是特别大的内存开销，时间复杂度比较重要。因为改进时间复杂度对算法的要求更高。” ——吴斌（NVidia，Graphics Architect）

同样是查找，如果是顺序查找需要O（n）的时间；如果输入的是排序的数组则只需要O（logn）的时间；如果事先已经构造好了哈希表，那查找在O（1）时间就能完成。我们只有对常见的数据结构和算法都了然于胸，才能在需要的时候选择合适的数据结构和算法来解决问题。

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

看到这道题很多应聘者就会想要是这个数组是排序的数组就好了。如果是排好序的数组，那么我们就能很容易统计出每个数字出现的次数。题目给出的数组没有说是排序的，因此我们需要先给它排序。排序的时间复杂度是O（nlogn）。最直观的算法通常不是面试官满意的算法，接下来我们试着找出更快的算法。

如果我们考虑到数组的特性：数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组『排序』，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说，这个数字就是统计学上的『中位数』，即长度为n的数组中第n/2大的数字。我们有成熟的O（n）的算法得到数组中任意第k大的数字。

在这一段很迷惑，是因为需要好好考虑下如何实现在 O(n) 的算法复杂度中找到任意第 k 大的数。『快速排序』第一趟排序之后，我们的到了一个中间索引（我们暂且称为 index），那么排在中间 index 前面的值都比 array[index] 小；同样的排序在中间 index 后面的元素都比 array[index] 大。第一趟的时间复杂度为O(n/2)。排序完之后，我们获得了两个子序列，同样根据上述的逻辑进行排序，假设当 k < index 时，那么我们就继续排序第二段比 index 小的部分。这一次的时间复杂度为O(n/4)。以此类推，当我们把 index 定位到 k 的时候，我们就会清楚的知道，在 k 以前的数字都比 array[k] 的值小。这也就快速的找到了任意 k 大的数组，时间复杂度 O ( n ) ≈ O ( n / 2 ) + O ( n / 4 ) + O ( n / 8 ) + ⋯ + O ( n / 2 n ) O(n) ≈ O(n/2)+O(n/4)+O(n/8)+ \dots + O(n/2^n) O(n)≈O(n/2)+O(n/4)+O(n/8)+⋯+O(n/2n)。参考的 java 代码可以如下：