Leetcode-面试题39-数组中超过一半的数字

Leecode-面试题39-数组中出现次数超过一半的数字

思路：哈希表/摩尔投票

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

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

Solution：

如果面试问到此题，别一上来就是摩尔投票法，要循序渐进（拖延时间）

1. 使用哈希表（普适性强，并考虑了数组中不存在满足条件的众数和数组为空的情况）

2. 摩尔投票法

• 票数和：由于众数出现的次数超过数组长度的一半；
  • 如果众数的票数记为+1 ， 非众数 的票数为 -1, 那么一定所有的票数和大于0
• 票数正负抵消：
  • 为构建正负抵消，假设数组首个元素 n1 为众数，遍历统计票数
  • 就算发生了正负抵消，剩余数组的众数一定不会变。如下图所示：

Java

Solution : 哈希表

// HashMap解法：
// 普适性强，并考虑了数组中不存在满足条件的众数和数组为空的情况
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        // 保证众数的条件
        // 数组中出现次数超过一半的数字
        int count = nums.length/2;


        for (int i = 0; i < nums.length; i++) {
            // 这个数字之前出现过
            if (map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i]) + 1);
            }else {
                // 这个数没出现过，初始化为1
                map.put(nums[i],1);
            }

            // 统计个数
            if (map.get(nums[i]) > count && i >= count){
                return nums[i];
            }
        }

        // 不存在数组中出现次数超过一半的数字
        return 0;
    }
}

• 时间复杂度： O(n) 遍历一遍数组
• 空间复杂度 ： O(n) 需要一个Map

Solution：摩尔投票法

class Solution{
    public int majorityElement(int[] nums) {
        int x = 0;
        int votes = 0;
        int count = 0;

        // 如果votes = 0 了，说明发生了正负抵消
        for (int num : nums) {
            if (votes == 0){
                // 则下一个数假定为众数
                x = num;
            }
            // 如果下一个数和众数相同 +1
            // 下一个和众数不同 -1
            votes += num == x? 1:-1;
        }

        // 验证x是否为众数
        for (int num : nums) {
            if (num == x){
                count++;
            }
        }

        // 判断这个众数是否超过一半的数组长度
        return count > nums.length/2? x:0;
    }
}

• 时间复杂度：O(N) N是nums的长度。
• 空间复杂度： O(1) 需要常数大小的额外空间。

Python

Solution :

打赏