剑指Offer系列（java版，详细解析）39.数组中出现次数超过一半的数字

ゝ一纸荒年。 2022-11-18 01:38 85阅读 0赞

# 题目描述 #

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

难度简单142收藏分享切换为英文接收动态反馈

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

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

**示例 1:**

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

**限制：**

1 <= 数组长度 <= 50000

# 测试用例 #

*  功能测试（输入的数组中存在一个出现次数超过数组长度一半的数字；输入的数组中不存在一个出现次数超过数组长度一半的数字）
 *  特殊输入测试（输入的数组中只有一个数字；输入空指针）

# 题目考点 #

*  考察应聘者对时间复杂度的理解。应聘者每想出一种解法，面试官都期待他能分析出这种解法的时间复杂度是多少。
 *  考察应聘者思维的全面性。面试官除了要求应聘者能对有效的输入返回正确的结果，同时也期待应聘者能对无效的输入进行相应的处理。

# 解题思路 #

## 直接解法 ##

先排序，如果存在出现次数大于数组长度一半的数，那么这个数必然在n/2位置上

排序的时间复杂度为O(nlogn)

## HashMap解码 ##

利用HashMap来统计数字出现的次数

时间复杂度不为O(1)

## 基于Partition函数的时间复杂度为O(n)的算法 ##

当数组中有一个数字出现的次数超过了数组长度的一半，那么这个数字一定是数组的**中位数**。

我们利用Partition函数找到中位数，然后判断这个数出现的次数是否真的超过数组长度的一半，如果是就输出这个数，不然就不存在超过数组长度一半的数，返回0。

代码太长，这里就不写了，可以参考之前的快速排序的Partition算法。

这种方法不好的地方是会修改输入的数组。

## 根据数组特点找出时间复杂度为O(n)的算法 ##

首先要明确一点：如果数组中一个数字出现的次数超过数组长度的一半，那么这个数字出现的次数比其他所有数字出现的次数之和还要多。

我们可以在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是该数组出现的次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为0，那么我们需要保存下一个数字，并把次数设为1，由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

这其实是一个投票问题，见补充。

# 参考解题 #

class Solution { 
        public int majorityElement(int[] nums) { 
            int x = 0, votes = 0, count = 0;
            for(int num : nums){ 
                if(votes == 0) x = num;
                votes += num == x ? 1 : -1;
            }
            // 验证 x 是否为众数
            for(int num : nums)
                if(num == x) count++;
            return count > nums.length / 2 ? x : 0; // 当无众数时返回 0
        }
    }

# 补充 #

1.  [Boyer-Moore Majority Vote][]

[Offer 39.]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[Boyer-Moore Majority Vote]: https://www.jianshu.com/p/dfd676b71ef0