剑指offer第二版-39.数组中出现次数超过一半的数字

本系列导航：剑指offer（第二版）java实现导航帖

面试题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