题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
思路：解法一、排序完后返回arr[N/2] O(nlgn) Arrays.sort(arr); System.out.println(arr[N/2]);
解法二、hash统计
解法三、顺序统计，就跟寻找乱序数组中第K大的数解法一样。O(N)，那么这里就是求乱序数组中第N/2大的数，限制：需要改动数组的内容
解法四、不同的数，进行消除
代码：
public class MoreThanHalf {
public static void main(String[] args) {
f(new int[]{5,6,6,6,2,3,6});
}
// 不同的数，进行消除，O(N)
public static void f(int arr[]){
//候选数 先定位第一个元素
int candidate = arr[0];
// 出现的次数
int nTimes = 1;
// 扫描数组
for (int i = 1; i < arr.length; i++) {
// 两两消减为0，应该把现在的元素作为候选值
if (nTimes==0 ) {
candidate = arr[i];
nTimes = 1;
continue;
}
// 如果遇到和候选值相同的，次数加一
if (arr[i]==candidate) {
nTimes++;
// 不同的数，进行消减
}else {
nTimes--;
}
}
//System.out.println(nTimes);
if (nTimes==0) {
System.out.println(-1);
}else {
System.out.println(candidate);
}
}
}
结果：
趣味拓展：加强版水王问题，假如出现的次数恰好为个数的一般，求出这个数。
思路：有个巧妙的方法扫描一遍数组就解决问题，水王发的贴子占总数的一半，说明总数为偶数；不失一般性，假设隔一个数就是水王的id，两两不同最后一定会消减为0，如果水王是最后一个元素，那么每次扫描的时候，多一个动作，和最后一个元素做比较，单独计数，计数恰好一半。如果不是，那么去掉最后一个元素，水王就是留下的那么candidate。
代码：
public class MoreThanHalf {
public static void main(String[] args) {
//进行测试数据要满足测试条件 不然结果会错误
f(new int[]{6,6,6,5,6,1,2,3,4,6});
}
// 不同的数，进行消除，O(N)
public static void f(int arr[]){
//候选数 先定位第一个元素
int candidate = arr[0];
// 出现的次数
int nTimes = 1;
int countOfLast = 1; // 统计这个元素出现的次数
// 扫描数组
for (int i = 1; i < arr.length; i++) {
if (arr[i-1]==arr[arr.length-1]) {
countOfLast++;
}
// 两两消减为0，应该把现在的元素作为候选值
if (nTimes==0 ) {
candidate = arr[i];
nTimes = 1;
continue;
}
// 如果遇到和候选值相同的，次数加一
if (arr[i]==candidate) {
nTimes++;
// 不同的数，进行消减
}else {
nTimes--;
}
}
//System.out.println(nTimes);
if (countOfLast==arr.length/2) {
System.out.println(arr[arr.length-1]);
}else {
System.out.println(candidate);
}
}
}
结果：