1-剑指offer: 数组中出现次数超过一半的数字
2024-10-20 07:41:50
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
代码:
// 至少三种方法
// 1. 遍历统计每个数字次数(O(n^2))
// 2. 借助快排思想(O(n))
// 3. 设置两个标志位,一个用于记录当前数字,另一个用于计数:向后遍历,当遇到相同的数字时,计数加1;
// 当遇到不同的数字时,计数减一;并且当计数为0时,替换为当前数字,计数置为1,继续往后遍历,直到数组最后.(O(n))
//
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if (numbers.size() == 0)
return 0;
int current_num = numbers[0];
int cnt = 1;
for (std::string::size_type index = 1; index < numbers.size(); index++) {
if (numbers[index] == current_num) {
cnt++;
} else {
cnt--;
if (!cnt) {
if (index == numbers.size()-1)
return 0;
current_num = numbers[index];
cnt = 1;
}
}
}
return current_num;
}
};
需要注意容易犯错的地方在于如果最后不做检查,很容易导致最后返回的是最后的值,而不会返回0.
最新文章
- javascript数据结构与算法--基本排序算法分析
- HTML5标签学习之~~~
- JavaScript编程异步助手:Promise
- Js获取URL中的QueryStirng字符串
- 《算法导论》习题解答 Chapter 22.1-4（去除重边）
- HDU1973 http://acm.hdu.edu.cn/showproblem.php?pid=1973
- C#基础（二）——C#中的构造函数
- 在用VS2010连接oracle数据库时ORA-12504错误
- oracle-行转列
- Android的布局优化之include、merge 、viewstub
- javascript笔记6之函数
- PHP标准库（SPL）- SplDoublyLinkedList类（双向链表）
- jpush 延迟推送的栗子
- Chrome浏览器读写系统剪切板
- vue实例属性的方法
- EDI 学习开发（一）
- #189 stat（动态规划）
- Atcoder 乱做
- 【解惑】领略Java内部类的“内部”
- Excel使用