评论

收藏

[C++] 基于visual Studio2013解决面试题之0802数字最多元素

编程语言 编程语言 发布于:2021-07-17 11:29 | 阅读数:560 | 评论:0

DSC0000.jpg

题目
DSC0001.jpg

解决代码及点评  
/*
查找数组中超过一半的那个元素
方法1:每次删除数组中一对不相同的value,最后剩下都是想通的数字时,就是超过一半的那个元素了
方法2:排序后,取中间元素即可
*/

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
int findSingle1(int a[] ,int len)//一遍扫描法
{
int tmp = a[0];
int count = 1;
for(int i=1;i<len;i++)
{
if(count == 0)
{
tmp = a[i];
count++;
continue;
}
if(a[i] == tmp)
count++;
else{
count--;
}
}
return tmp;
}
int findSingle2(int a[], int len)//hashmap 统计
{
map<int,int> imap;
map<int,int>::iterator it ;
for(int i=0;i<len;i++)
{
it = imap.find(a[i]);
if(it!=imap.end())
{
(*it).second++;
}else{
imap[a[i]] = 1;
}
}
it = imap.begin();
while(it!=imap.end())
{
if((*it).second > len/2)
return (*it).first;
it++;
}
return -1;
}
//排序后取中间元素
int findSingle3(int a[],int len)
{
sort(a,a+len);
return a[len/2];
}
int main()
{
int a[] = {1,3,4,8,5,1,2,5,5,5,5,5,5};
int len = sizeof(a)/sizeof(int);
cout<<findSingle3(a,len)<<endl;
system("pause");
return 0;
}
 代码下载及其运行代码下载地址:http://download.csdn.net/detail/yincheng01/6704519
解压密码:c.itcast.cn
下载代码并解压后,用VC2013打开interview.sln,并设置对应的启动项目后,点击运行即可,具体步骤如下:
1)设置启动项目:右键点击解决方案,在弹出菜单中选择“设置启动项目”
DSC0002.jpg

2)在下拉框中选择相应项目,项目名和博客编号一致
DSC0003.jpg

3)点击“本地Windows调试器”运行
DSC0004.jpg

程序运行结果
DSC0005.jpg





分享到: QQ好友和群QQ好友和群
评论

使用道具 举报