题:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
思路:首先看到这个题目,数组中一个数字出现的次数超过数组长度的一半,也就意味着这个数字出现的次数比数组中其它数字出现次数的总和还多。我们在遍历的数组的时候可以用两个值来记录,一个是数组出现的次数count,一个用来保存它的结果result,我们把数组的第一个数arr[0]作为结果保存跟下一个数字比较,count记为1,如果下一个数字跟之前保存的数字相同count+1,如果跟之前保存的数字不同,则count-1。如果次数为0,我们需要保存它的下一个数字,并且将次数设为1。因为要找的数字出现的次数超过数组长度长度的一半,所以最后一次设为1的数字就是我们要找的数字。
代码:
#include <iostream>
using namespace std;
int Serach(int arr[],int len)
{
int count=1;
int result=arr[0];
for(int i=1;i<len;i++)
{
if(count==0)
{
result=arr[i];
count=1;
}
else if(result == arr[i])
count++;
else
count--;
}
return result;
}
int main()
{
int arr[]={1,2,3,2,2,2,5,4,2};
int sz=sizeof(arr)/sizeof(arr[0]);
int ret=Serach(arr,sz);
cout<<ret<<endl;
return 0;
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。