首页 / 面试 / 面试题29：数组中出现次数超过一半的数字
面试题29：数组中出现次数超过一半的数字
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试题29：数组中出现次数超过一半的数字，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1313字，纯文字阅读大概需要2分钟。
内容图文
O(n)的解法：
考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1。如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。
原理就是如果确实存在出现次数超过一半的数字，那么他出现的次数一定可以抵消掉没有其他数字出现的次数。当然如果输入的例子不对也可能通过，所以最后需要检查
1
bool g_bInputInvalid = false;
2 3bool CheckInvalidArray(int* numbers, int length)
4{
5 g_bInputInvalid = false;
6if(numbers == NULL && length <= 0)
7 g_bInputInvalid = true;
8 9return g_bInputInvalid;
10}
1112bool CheckMoreThanHalf(int* numbers, int length, int number)
13{
14int times = 0;
15for(int i = 0; i < length; ++i)
16 {
17if(numbers[i] == number)
18 times++;
19 }
2021bool isMoreThanHalf = true;
22if(times * 2 <= length)
23 {
24 g_bInputInvalid = true;
25 isMoreThanHalf = false;
26 }
2728return isMoreThanHalf;
29}
3031int MoreThanHalfNum_Solution2(int* numbers, int length)
32{
33if(CheckInvalidArray(numbers, length))
34return0;
3536int result = numbers[0];
37int times = 1;
38for(int i = 1; i < length; ++i)
39 {
40if(times == 0)
41 {
42 result = numbers[i];
43 times = 1;
44 }
45elseif(numbers[i] == result)
46 times++;
47else48 times--;
49 }
5051if(!CheckMoreThanHalf(numbers, length, result))
52 result = 0;
5354return result;
55 }
原文：http://www.cnblogs.com/raichen/p/5655438.html
内容总结
以上是互联网集市为您收集整理的面试题29：数组中出现次数超过一半的数字全部内容，希望文章能够帮你解决面试题29：数组中出现次数超过一半的数字所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。