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

剑指 Offer 39. 数组中出现次数超过一半的数字 题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
复制代码

代码：

class Solution {
    public int majorityElement(int[] nums) {
          // 法一：可直接对数组排序，取中间那个元素，即为超过一半的数字
          // 法二：利用map，遍历数组元素，记下每个元素出现的次数
          int repeat  = 0;
          HashMap<Integer, Integer> map = new HashMap<>();
          for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
          }
          for (Integer integer : map.keySet()) {
            if (map.get(integer) > nums.length/2){
               repeat = integer;
            }
          }
          return repeat;
}
}
复制代码

image.png