剑指leetcode—数组中出现次数超过一半的数字

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

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

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

限制：
1 <= 数组长度 <= 50000

这道题目有多种解法

方法一：

哈希表统计法

建立哈希表统计nums中数字的数量，对应的数字为键，键值为数字的数量。当某一个数字的键值超过数组的一半长度时，该数字就是众数。

class Solution{
    public int majorityElement(int [] nums)
    {
        HashMap<Integer,Integer> map=new HashMap<>();
        int length=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
            {
                map.put(nums[i],1);
            }
            if(map.get(nums[i])>length)
            return nums[i];
        }
        return 0;
    }
}

方法二：

数组排序法

利用效率较高的算法排序数组，例如快速归并排序，堆排序，然后由于众数的数量超过数组长度的一半，所以数组中点的元素一定就是众数，算法的时间复杂度为O(Nlog2N)

方法三：

摩尔投票法（这方法好稀奇）

首先定义几个概念

• 票数和：由于众数出现的次数超过数组长度的一半；若记众数的票数为+1，非众数的票数为-1，则一定有所有数字的票数和大于0
• 票数抵消：设置nums中的众数为x，数组长度为n，若nums的前a个数字的票数和为0，则数组后面n-a个数字的票数和一定大于0，也就是说后面n-a个数字中的众数还是x。

算法原理：

• 为构建正负抵消，假设数组中的首个元素n是众数，遍历统计票数，当发生正负抵消时，剩余数组的众数一定不变，因为（设置真正的众数为x）

  • 当n==x：抵消的所有数字中，有一半是众数
  • 当n！=x，抵消的所有数字中，少于等于一半是众数

• 每轮假设都可以缩小剩余数组的区间，遍历结束，最后一轮假设的数字就是众数。众数超过一半，最后一轮的票数和必定为正数

class Solution{
	public int majorityElement(int [] nums){
	int x=0,votes=0;
	for(int num:nums){
	if(votes==0)
	x=num;
	votes+=num==x? 1:-1;
	}
	return x;
	}
}	

最后

以上就是昏睡小伙为你收集整理的剑指leetcode—数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决剑指leetcode—数组中出现次数超过一半的数字所遇到的程序开发问题。

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