剑指offer（28）

题目描述

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

题目分析

这题也有两种做法：

第一种：基于快排思想中的partition函数来做，因为根据题目，那么排序后的数组中间的数就是那个出现次数超过一半的数，那么我只需要利用快排中的partition，找到数组中间的那个数就行。

类似于之前写的查找第K大的数，只不过现在的K值为数组长度的一半

第二种：根据数组特点来做，数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数的和还要多，那么就可以从这里下手啦，具体看代码。

第一种要修改数组，第二种不需要修改数组。除此之外，注意检查是不是符合要求。

代码

第一种：

function MoreThanHalfNum_Solution(numbers)
{
    if(!numbers.length) return 0;
    if(numbers.length==1) return numbers;
    let halfLen=~~((numbers.length)/2);
    let res=search(numbers,0,numbers.length-1,halfLen);
    if(!checkMoreThanHalf(numbers,res)){
        return 0;
    }
    return res;
}
function search(numbers,left,right,k)
{
    let key=partition(numbers,left,right);
    if(left<right){
        key=partition(numbers,left,right);
        let len=right-key+1;
        if(len==k){//重点，递归的结束条件
            return numbers[key];
        } else if(len>k){
            return search(numbers,key+1,right,k);
        } else{
            return search(numbers,left,key-1,k-len);
        }
    }
}
function partition(a,left,right){
    let key=a[left];//一开始让key为第一个数
    while(left<right){//扫描一遍
        while(key<=a[right]&&left<right){//如果key小于a[right]，则right递减，继续比较
            right--;
        }
        [a[left],a[right]]=[a[right],a[left]];//交换
        while(key>=a[left]&&left<right){//如果key大于a[left]，则left递增，继续比较
            left++;
        }
        [a[left],a[right]]=[a[right],a[left]];//交换
    }
    return left;//把key现在所在的下标返回
}
function checkMoreThanHalf(numbers,num) {
    let times=0;
    for(let i=0;i<numbers.length;i++){
        if(num==numbers[i]){
            times++;
        }
    }
    if(times*2<=numbers.length){
        return false;
    }else return true;
}

第二种：

function MoreThanHalfNum_Solution(numbers)
{
    let res=numbers[0],times=1;
    for(let i=0;i<numbers.length;i++){
        if(times==0){
            res=numbers[i];
            times=1;
        }else if(numbers[i]==res){
            times++;
        }else{
            times--;
        }
    }
    if(!checkMoreThanHalf(numbers,res)){
        res=0;
    }
    return res;
}
function checkMoreThanHalf(numbers,num) {
    let times=0;
    for(let i=0;i<numbers.length;i++){
        if(num==numbers[i]){
            times++;
        }
    }
    if(times*2<=numbers.length){
        return false;
    }else return true;
}