首页 > 代码库 > 数组中超过出现次数一半的数字 【微软面试100题 第七十四题】
数组中超过出现次数一半的数字 【微软面试100题 第七十四题】
问题要求：
数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
参考资料：编程之美2.3 寻找发帖水王
问题分析：
方法1 对数组排序，然后顺次查找其中最多的；
方法2 对数组排序，最中间一个肯定为要找的数字,时间复杂度O(NlogN)；
方法3 每次消去数组中两个不同的数，最后剩下的肯定为要找的数字，时间复杂度O(N).
方法3代码1如下，以下是图解代码1
代码实现：
//代码1
#include <stdio.h>
int Find(int* ID, int N);
int main(void)
{
int ID[30] = {5,6,7,1,2,1,2,1,2,3,3,4,3,2,1,3,2,1,2,1,3,1,1,1,1,1};
printf("水王id: %d\n",Find(ID,30));
return 0;
}
int Find(int* ID, int N)
{
int candidate;
int nTimes, i;
for(i = nTimes = 0; i < N; i++)
{
if(nTimes == 0)
{
candidate = ID[i], nTimes = 1;
}
else
{
if(candidate == ID[i])
nTimes++;
else
nTimes--;
}
}
return candidate;
}扩展问题1：
如果改为该数字长度为数组长度的一半，又该如何求？
问题分析：
先消掉3个不同的id，再使用代码1的方法求解。因为消除3个不同id时，水王id最多消除一个，则，这样之后水王id个数就大于总数的一半了，就变成原问题了。
代码实现：
#include <stdio.h>
int Find(int* ID, int N);
int main(void)
{
int ID[6] = {2,1,2,1,3,1};
printf("水王id: %d\n",Find(ID,6));
return 0;
}
int Find(int* ID, int N)
{
int candidate;
int nTimes = 0, i;
int flag = 0;
int del[3];
del[0] = ID[0];
for(i = 1; i < N; i++)
{
if((ID[i] != del[0]) && (flag == 0))
{
del[1] = ID[i];
flag = 1;
continue;
}
if((ID[i] != del[0]) && (ID[i] != del[1]) && (flag == 1))
{
flag = 2;
continue;
}
if(nTimes == 0)
{
candidate = ID[i], nTimes = 1;
}
else
{
if(candidate == ID[i])
nTimes++;
else
nTimes--;
}
}
return candidate;
}扩展问题2：
如果数组中的3个数字个数都分别超过了数组长度的1/4，又该如何查出它们？
问题分析：
每次绑定三个id，同时加减。
代码实现：
#include <stdio.h>
void Find(int* ID, int N);
int main(void)
{
int ID[] = {5,6,7,1,2,1,2,1,2,3,3,4,3,2,1,3,2,1,2,1,3};
Find(ID,21);
return 0;
}
void Find(int* ID, int N)
{
int nTimes[3], i;
int candidate[3];
nTimes[0]=nTimes[1]=nTimes[2]=0;
candidate[0]=candidate[1]=candidate[2]=-1;
for(i = 0; i < N; i++)
{
if(ID[i]==candidate[0])//这几个并列的思想很重要，好好想想
{
nTimes[0]++;
}
else if(ID[i]==candidate[1])
{
nTimes[1]++;
}
else if(ID[i]==candidate[2])
{
nTimes[2]++;
}
else if(nTimes[0]==0)
{
nTimes[0]=1;
candidate[0]=ID[i];
}
else if(nTimes[1]==0)
{
nTimes[1]=1;
candidate[1]=ID[i];
}
else if(nTimes[2]==0)
{
nTimes[2]=1;
candidate[2]=ID[i];
}
else//新的id和已选的三个id不同的时候，让已选的三个id同时-1
{
nTimes[0]--;
nTimes[1]--;
nTimes[2]--;
}
}
printf("id: %d %d %d\n",candidate[0],candidate[1],candidate[2]);
printf("times:%d %d %d\n",nTimes[0],nTimes[1],nTimes[2]);
return;
}数组中超过出现次数一半的数字 【微软面试100题 第七十四题】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。