题目地址(39. 数组中出现次数超过一半的数字)

https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

题目描述

  1. 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
  5. 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
  9. 示例 1:
  11. 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
  12. 输出: 2
  16. 限制：
  18. 1 <= 数组长度 <= 50000
  22. 注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/

前置知识


公司

  • 暂无

思路

众数是大于数组一半的数 就可以了
还可以使用摩尔投票法

关键点


代码

  • 语言支持：Java

Java Code:
hash表

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         int count  = nums.length/2;
  4.         HashMap<Integer, Integer> map = new HashMap<>();
  5.         for (int i = 0; i < nums.length; i++) {
  6.             if (map.containsKey(nums[i])) {
  7.                 map.put(nums[i], map.get(nums[i]) + 1);
  8.             }else{
  9.                 map.put(nums[i], 1);
  10.             }
  11.             if (map.get(i) > count) {
  12.                 return nums[i];
  13.             }
  14.         }
  15.         return 0;
  16.     }
  17. }

排序

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

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 39. 数组中出现次数超过一半的数字 - 图1#card=math&code=O%28n%29&id=GgXcX)
  • 空间复杂度：剑指 Offer 39. 数组中出现次数超过一半的数字 - 图2#card=math&code=O%28n%29&id=s9GAb)