剑指 Offer 39. 数组中出现次数超过一半的数字

169. 多数元素

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入输出

1
2
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

基本思路

摩尔投票法 知乎分析简明易懂

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

算法流程:

  • 初始化： 票数统计 votes = 0 ， 众数 x；
  • 循环： 遍历数组 nums 中的每个数字 num ；
    • 当 票数 votes 等于 0 ，则假设当前数字 num 是众数；
    • 当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 ；
  • 返回值： 返回 x 即可；
  • 后边可再加上判断是否存在众数(加与不加都能通过)

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 脑机急转弯了属于是...但是不符合 时复O(nlogn) 空复O(logn)
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0, count = 0;
        for(int num:nums){
            if(votes == 0) x = num;
            votes += num == x?1:-1;
        }
        for(int num : nums){
            if(num == x) count++;
        }
        return count > nums.length / 2 ? x : 0;
    }
}