数据结构与算法-求众数

Posted by 周思进 on September 20, 2019

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/majority-element

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3] 输出: 3 示例 2:

输入: [2,2,1,1,1,2,2] 输出: 2


想到的还是穷举法…,把每个数在数组中遍历一遍,看其个数是否超过一半。

int majorityElemen(int* nums, int numsSize){
    int i = 0;
	int j = 0;
	int res = 0;
	int cnt = 0;
    
    for (i = 0; i < numsSize; i++)
	{
		res = nums[i];
        cnt = 1;

		for (j = 1; j < numsSize; j++)
		{
			if (res == nums[j])
			{
				cnt++;
			}
		}

		if (cnt > numsSize/2)
		{
			printf("res : %d\n", res);
			return res;
		}
	}

	return 0;
}

搞完一跑,系统提示超出时间限制…

其他没想到解决方案,思路好匮乏,忧伤… 算法之路真是还有好长要走。


查看官方解答,还有如下解法

1、排序
根据众数的特性,其个数大于n/2,那么将数组排序后,数组下标n/2所对应的数据一定是众数。


2、随机法
因为超过一半的数是所要查找的数,所以可能随机选择一个数就是众数,随机选择一个数之后,再依次遍历一遍所有数据,确认是否个数超过一半。

还有哈希表和分治算法,暂时先不去研究了。


最后看到还有投票法,真是绝了…
众数的当做投赞成票加1,不是众数的投反对票减1,两票就当作废了,重新开始计票。
新拿到的这张票先预设是众数,当成赞成票,如果计数被减到0了,则重新拿下一张票当做众数,最后手持的一定是众数。

int majorityElement_boyer(int* nums, int numsSize){
	int i = 0;
	int cnt = 0;
	int res = 0;

	for (i = 0; i < numsSize; i++)
	{
		if (cnt == 0)
		{
			res = nums[i];
			cnt++;
		}
		else
		{
			if (nums[i] == res)
				cnt++;
			else
				cnt--;
		}
	}

	return res;
}

查看官方解答优化后的代码


int majorityElement_boyer_v2(int* nums, int numsSize){
	int i = 0;
	int cnt = 0;
	int res = 0;

	for (i = 0; i < numsSize; i++)
	{
		if (cnt == 0)
		{
			res = nums[i];
		}

		cnt += (nums[i] == res) ? 1 : -1;
	}

	return res;
}


最后网上还看到有位操作法…
想法就是整数32位,针对每一位遍历数组进行位操作计算,那一位统计的个数超过数组一半,那一定也是中位数需要的位,以此遍历32位得到最终结果。

// 位操作法
int majorityElement_bit(int* nums, int numsSize){
	int i = 0;
	int j = 0;
	int ones = 0;
	int zeros = 0;
	int res = 0;

	for (i = 0; i < 32; i++)
	{
		ones = 0;
		zeros = 0;
		for (j = 0; j < numsSize; j++)
		{
			if (nums[j] & (1 << i))
				ones++;
			else
				zeros++;	
		}

		if (ones > zeros)
			res |= (1 << i);
	}

	return res;
}