数据结构与算法-求众数

来源：力扣（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;
}

FEATURED TAGS