题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
分析：
如果一个数字才数组中出现的次数超过了数组长度的一半，那么对这个数组进行排序，位于数组中间位置的那个数就是出现次数超过一半的那个数。对数组排序的时间复杂度是O(nlog(n))，但是对于这道题目，还有更好的算法，能够在时间复杂度O(n)内求出。我们写过快速排序算法，其中的Partition()方法是一个最重要的方法，该方法返回一个index，能够保证index位置的数是已排序完成的，在index左边的数都比index所在的数小，在index右边的数都比index所在的数大。那么本题就可以利用这样的思路来解。
- 通过Partition()返回index，如果index==mid，那么就表明找到了数组的中位数；如果index<mid，表明中位数在[index+1,end]之间；如果index>mid，表明中位数在[start,index-1]之间。知道最后求得index==mid循环结束。
- 根据求得的index，遍历一遍数组，每当出现一个等于index所指向的数时time++，最后判断time是否大于数组长度的一半，如果大于则表明index所指向的数就是所求的数，如果不是，则表明不存在一个数出现的次数超过数组长度的一半。
代码实例：
View Code
题目变种
一个文件中有每一个保存一个单词，其中有一个单词出现的次数超过一半，求这个次数超过一半的单词。
解体思路
这道题目其实本质上跟前面的求出现次数超过一半的数是一样的，只不过是这里要求的是单词出现次数，而前面是整数出现次数。如果是整数的话，可以通过一个整型数组来完成求中位数的操作。但是这里是字符串了，我们想再用求中位数的方法，只能通过LinkedList这个集合累来完成。
首先我们遍历一次问价，将所有单词都保存到LinkedList当中去，然后求排在中间的那个单词。LinkedList中的元素使有序的，不像ArrayList中的元素那样是无序的。而且List中允许元素重复。
代码实现
View Code
本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/05/08/2489728.html，如需转载请自行联系原作者
