[剑指 Offer]数组中出现次数超过一半的数字

[剑指 Offer]数组中出现次数超过一半的数字

题目：

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

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

题解

方法一：哈希表统计法

• 将数组中的元素逐个存入map，key-num，val-个数
• put时val从map中获取，有就加一，没有就是1
• 判断数字出现的次数是否超过数组长度的一半，符合就可以返回了

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();

        for (int num : nums){
            map.put(num,map.getOrDefault(num,0)+1);
            if(map.get(num)> nums.length>>1) return num;
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11

方法二：排序取中位数

• 将数组 nums 排序，数组中点的元素 一定为众数

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

方法三：摩尔投票法

• 遍历数组中的每个元素，记录该数字的个数
• 开始时count == 0，将第一个数假设为众数
• 遇到相同的元素个数加1，不相同的个数减一，个数为零时改变众数
• 最后留下的就是 数组中出现次数超过一半的数字

class Solution {
    public int majorityElement(int[] nums) {
    	//count：个数，curr：当前假设的众数
        int count = 0,curr = 0;

        for (int num : nums){
            if (count == 0) curr = num;
            count += num == curr ? +1 : -1;
        }
        return curr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

---