首页 > 代码库 > 数组中超过出现次数一半的数字 【微软面试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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。