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

解题思路1：哈希表

算法流程：

  • 初始化 map；遍历数组，key 存储数组中的数字，value 统计该数字出现的次数
  • 遍历 map，找到 value > nums.length / 2 的 key 返回

代码

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         Map<Integer,Integer> map = new HashMap<>();
  4.         for(int num : nums){
  5.             if(map.containsKey(num)){
  6.                 map.put(num,map.get(num) + 1);
  7.             }else {
  8.                 map.put(num,1);
  9.             }
  10.         }
  11.         for(Map.Entry<Integer,Integer> entry : map.entrySet()){
  12.             if(entry.getValue() > nums.length / 2){
  13.                 return entry.getKey();
  14.             }  
  15.         }
  16.         return -1;
  17.     }
  18. }

复杂度分析

  • 时间复杂度：O(N + K)

遍历数组 nums ，统计每个数字出现的次数的时间复杂度为 O(N)，遍历哈希表，找到众数的时间复杂度为 O(K)

  • 空间复杂度的：O(K)

我们使用哈希表存储数组中不相同的数字，使用额外的空间为 O(K)

解题思路2：排序

数组当中有一个数字出现的次数超过数组长度的一半，如果对该数组进行排序，那么众数必然位于数组的中间。

代码

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         Arrays.sort(nums);
  4.         return nums[nums.length / 2];
  5.     }
  6. }

复杂度分析

  • 时间复杂度：O(N * logN)

排序的时间复杂度为 O(N * logN)

  • 空间复杂度：O(1)

解题思路3：数学

本题最佳的解法为 摩尔投票法

摩尔投票的核心概念是票数正负抵消

  • 众数的票记作为 +1，非众数的票记作为 -1，则一定有所有数字的票数和大于 0

算法流程：

  • 初始化：设定众数为 x，票数统计为 votes = 0

  • 循环：

    • 当 votes == 0 时，则假设当前数字 num 为众数
    • 当 num == x 时，votes++；当 num != x 时，votes—

  • 结果返回 x

代码

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         int votes = 0;
  4.         int x = 0;
  5.         for(int num : nums){
  6.             if(votes == 0){
  7.                 x = num;
  8.             }
  9.             votes = x == num ? ++votes : --votes;
  10.         }
  11.         return x;
  12.     }
  13. }

复杂度分析

  • 时间复杂度：O(N)

  • 空间复杂度：O(1)