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