面试题39：数组中出现次数超过一半的数字
题目要求：
找出数组中出现次数超过数组长度一半的数字。如输入{1,2,3,2,2,2,5,4,2}，则输出2。
解题思路：
因为该数字的出现次数超过了数组长度的一半，因此可以将问题转化为求数组的中位数。如果按照这个思路，有以下两种方式解决：排序后求中位数、用快排的分区函数求中位数（topK问题），这两种思路都比较简单，此处不再赘述。
书中还提到一种思路，相当巧妙，可以看作一种特殊的缓存机制。该思路需要一个整型的value变量和一个整型的count变量，记录缓存值与该缓存值被命中的次数。缓存规则以及执行步骤如下：
步骤1： 缓存值value，命中次数count均初始化为0。
步骤2： 从头到尾依次读取数组中的元素，判断该元素是否等于缓存值：
步骤2.1：如果该元素等于缓存值，则命中次数加一。
步骤2.2：如果该元素不等于缓存值，判断命中次数是否大于1：
步骤2.2.1：如果命中次数大于1，将命中次数减去1。
步骤2.2.2：如果命中次数小于等于1，则令缓存值等于元素值，命中次数设为1
步骤3： 最终的缓存值value即为数组中出现次数超过一半的数字。
此方法时间复杂度o(n)，空间复杂度o(1)，实现简单。
package chapter5;
/**
* Created with IntelliJ IDEA.
* Author: ryder
* Date : 2017/7/28
* Time : 17:51
* Description: 数组中出现次数超过一半的数字
**/
public class P205_MoreThanHalfNumber {
//转化为topK问题（此处求第k小的值），使用快排的分区函数解决，求第targetIndex+1小的数字（下标为targetIndex）
//书中说这种方法的时间复杂度为o(n)，但没懂为什么。网上也有人说为o(nlogk)
public static int moreThanHalfNum1(int[] data){
if(data==null || data.length==0)
return 0;
int left = 0,right=data.length-1;
//获取执行分区后下标为k的数据值（即第k+1小的数字）
int k = data.length>>>1;
int index = partition(data,left,right);
while(index!=k){
if(index>k)
index = partition(data,left,index-1);
else
index = partition(data,index+1,right);
}
return data[k];
}
//分区，[小，povot，大]
public static int partition(int[] data,int left,int right){
int pivot = data[left];
while(left<right){
while (left<right && data[right]>=pivot)
right--;
if(left<right)
data[left] = data[right];
while (left<right && data[left]<pivot)
left++;
if(left<right)
data[right] = data[left];
}
data[left] = pivot;
return left;
}
//根据数组特点进行记录、查找，时间复杂度o(n)
public static int moreThanHalfNum2(int[] data){
if(data==null || data.length==0)
return 0;
int count = 1;
int value = data[0];
for(int i=1;i<data.length;i++){
if(data[i]==value)
count++;
else if(data[i]!=value && count==1)
value = data[i];
else
count--;
}
return value;
}
public static void main(String[] args){
int[] data = {1,2,3,2,2,2,5,4,2};
System.out.println(moreThanHalfNum2(data));
System.out.println(moreThanHalfNum1(data));
}
}
运行结果
2
2
