寻找多数元素

问题描述：求n个元素序列中的多数元素，多数元素为在序列中出现的次数多于n/2的元素。

非递归实现

摩尔投票算法

function getMultipleNum(nums){
    if(nums.length === 0) return null; // 如果数组为空，返回null
    if(nums.length === 1) return nums[0]; // 如果数组只有一个元素，直接返回该元素
    //分别求左右两半边的多数元素
    const leftHalf=nums.slice(0, Math.floor(nums.length / 2));
    const rightHalf=nums.slice(Math.floor(nums.length / 2));
    const leftMajority=getMultipleNum(leftHalf);
    const rightMajority=getMultipleNum(rightHalf);
 
    //如果两边的多数元素相同，则该元素为多数元素
    if(leftMajority === rightMajority){
        return leftMajority;
    }
    //如果不同，分别统计两边多数元素在整个当前序列中出现的次数，只有超过n/2的才是多数元素
    else{
        const leftCount=nums.filter(num => num === leftMajority).length;
        const rightCount=nums.filter(num => num === rightMajority).length;
        if(leftCount > Math.floor(nums.length / 2)){
            return leftMajority;
        }else if(rightCount > Math.floor(nums.length / 2)){
            return rightMajority;
        }else{
            return null; // 没有多数元素
        }
    }
}

reference