数组中出现次数超过一半的数字

思路一：计算每个数字出现的次数

这是常规思路，遍历数组并记录当前数字出现的次数，可以采用hash表(js中用Map类型)来记录。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let m = new Map();
    for(let num of nums){
        m.has(num) ? m.set(num, m.get(num)+1) : m.set(num, 1);
        if(m.get(num)>nums.length/2) return num;
    }
};

时间复杂度和空间复杂度都是O(n)。

思路二：排序找中位数

要找的这个数字出现次数超过了一半，那么排序后中位数一定是这个数字。

• 利用快排来划分，划分后枢轴所在位置如果小于 n/2，则中位数在右边，继续划分；
• 反之如果划分后枢轴所在位置大于 n/2，则中位数在左边，也继续划分。
• 直到划分完枢轴所在位置 正好等于 n/2，即该位置的数为中位数。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    
    let start = 0;
    let end = nums.length-1;
    let middle = Math.floor(nums.length / 2);
    let idx = partition(nums, start, end);
    while(idx!=middle){
        if(idx<middle){
            start = idx + 1;
            idx = partition(nums, start, end)
        }else{
            end = idx - 1;
            idx = partition(nums, start, end);
        }
    }
    return nums[idx];
};

var partition = function(nums, left, right){
    let pivot = nums[left];
    while(left<right){
        while(left < right && nums[right]>=pivot) right--;
        nums[left] = nums[right];
        while(left < right && nums[left]<=pivot) left++;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

时间复杂度剑指offer上写的是O(n)，但我觉得似乎是O(nlogn)?
空间复杂度O(1)。

思路三：寻找众数

• 数组中删除两个不同的数，不改变整个数组的众数。
• count--就相当于去除两个不同的数。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    if(nums.length<1) return false;
    let res = nums[0]
    let count = 0;
    for(let num of nums){
        if(count===0) res = num;
        num===res ? count++ : count--;
    }
    // 若存在众数，则res必定为众数。
    // 若不存在众数，则res只是数组局部的众数。
    count = 0;
    for(let num of nums){
        if(num===res) count++;
        if(count>nums.length/2) return res;
    }
    return false;
};

时间复杂度为O(n)，空间复杂度为O(1)。

最后

以上就是能干饼干为你收集整理的数组中出现次数超过一半的数字数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决数组中出现次数超过一半的数字数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。