遇到这个题最简单的想法就是,统计每个元素出现的次数。但是无法知道数组中有多少种元素,并且这样会用到其他的存储空间,再查找结果的时候也需要多遍历一次结果的数组。
正确的解决办法是去记录重复元素(不管是否是结果元素)的数量,然后碰见一个不同元素就减一(相当于抵消了),碰见结果元素也是一样的。
思考一下,结果元素会超出一半,所以当所有不同元素被抵消完肯定还会剩下结果元素。
这种方法只遍历一次数组。
int FindNum(int *a, int n){ int result = a[0]; int result_count = 1; for (int i = 1; i < n; i++) { if (a[i]==result) { result_count++; } else { result_count--; if (result_count==0) { result = a[i]; result_count = 1; } } } return result;}
完整版
int FindNum(int *a,int len)
{
int result = a[0];
int result_count = 1;
for (int i = 1; i < len; i++)
{
if (a[i] == result)
{
result_count++;
}
else
{
result_count--;
if (result_count == 0)
{
result = a[i];
result_count = 1;
}
}
}
return result;
}
int main()
{
int a[] = {1,3,2,3,3,4,3,3,3};
int len = sizeof(a) / sizeof(a[0]);
int res = FindNum(a,len);
cout << res << endl;
system("pause");
return 0;
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。