问题

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为O(N)、空间复杂度为O(1)的解决方案

示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5

示例 2：
输入：[3,2]
输出：-1

示例 3：
输入：[2,2,1,1,1,2,2]
输出：2

哈希表

  1. class Solution(){
  2.     public int majorityElement(int[] nums){
  3.         int n = nums.length;
  4.         Map<Integer, Integer> map = new HashMap<>();
  6.         for(int x : nums){
  7.             map.put(x, map.getOrDefault(x, 0) + 1);
  8.             if(map.get(x) > n / 2) return x
  9.         }
  10.         return -1;
  11.     }
  12. }
  • 时间复杂度：面试题17.10.主要元素 - 图1
  • 空间复杂度：面试题17.10.主要元素 - 图2

摩尔投票

image.png

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         int candidate = -1;
  4.         int count = 0;
  5.         for (int num : nums) {
  6.             if (count == 0) {
  7.                 candidate = num;
  8.             }
  9.             if (num == candidate) {
  10.                 count++;
  11.             } else {
  12.                 count--;
  13.             }
  14.         }
  16.         count = 0;
  17.         int length = nums.length;
  18.         for (int num : nums) {
  19.             if (num == candidate) {
  20.                 count++;
  21.             }
  22.         }
  23.         return count * 2 > length ? candidate : -1;
  24.     }
  25. }