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

题目

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

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

思路

三种思路：数组中出现次数超过一半的数字相当于众数，求众数

方法一：哈希表

使用哈希表统计，遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数

方法二：排序

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

方法三：摩尔投票法

核心理念为 票数正负抵消 ，空间复杂度只需O（1），为本题的最佳解法

投票法简单来说就是不同则抵消，占半数以上的数字必然留到最后。

算法流程如下：

1. 初始化 票数统计 votes = 0 ， 出现次数超过一半的数字 x
2. 遍历数组 nums 中的每个数字 num
   （1）当票数votes == 0，则假设当前数字 num 是众数
   （2）当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1
3. 最后返回 x 即可

java代码如下：

class Solution{
	public int majorityElement(int[] nums){
		int x = 0, votes = 0;
		for(int num : nums){
			if(votes == 0){//当票数为0
				x = num;//则假设当前数字num是众数
			}
			votes += ( num == x ? 1 : -1);//当num等于x时，票数加一，否则减一
		}
		return x;
	}
}

最后

以上就是动听纸飞机为你收集整理的剑指 Offer 39. 数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决剑指 Offer 39. 数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。