数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0
版本一: map映射, 哈希法, 上午刚学到的现在用上了
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
std::unordered_map<int, int> hash_map;
for (int i = 0; i < numbers.size(); i++) {
hash_map[numbers[i]] += 1;
}
for (int i = 0; i < numbers.size(); i++) {
if (hash_map[numbers[i]] > (numbers.size() / 2)) { // ----> 此处用的是大于, 而不是大于等于
return numbers[i];
}
}
return 0;
}
};
思想: 依次遍历数组, 设置两个值, 一个是临时数字, 一个是次数, 依次遍历数组, 相同+1, 不相同-1, 0时更新当前临时数字
注意: 当数组中存在大于数组一半的数组时, 这个临时数字就是要该数字, 否则该临时数字保存的值不确定, 所以用第二个for检验出现次数;
改进这种方法好像可以统计数组中连续N出现的数字是哪个(会举一反三了, 哈哈)
/* 若没有第二个for判断出现次数, 第一个数组重复次数交替出现, 临时数字是3
{ 1, 2, 3, 2, 4, 2, 5, 2, 3}
{ 1, 2, 3, 5, 4, 2, 2, 2, 3 }
*/
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if (numbers.empty()) {
return 0;
}
int size = numbers.size();
int temp = numbers[0];
int times = 1;
// 找出重复次数最多的数字, 该数字并不一定就是大于数组一半
for (int i = 1; i < size; i++) {
if (numbers[i] == temp) {
times++;
}
else {
times--;
}
if (0 == times) {
temp = numbers[i];
times = 1;
}
}
// 确定重复多少次
times = 0;
for (int i = 0; i < size; i++) {
if (numbers[i] == temp) {
times++;
}
}
// 判断重复次数是否大于数组的一半
if (times > (size / 2)) {
return temp;
}
else {
return 0;
}
}
};
我的测试
#include <iostream>
#include <vector>
using namespace std;
int MoreThanHalfNum_Solution(vector<int> numbers) {
int n = numbers.size();
if (n == 0) return 0;
int num = numbers[0], count = 1;
for (int i = 1; i < n; i++) {
if (numbers[i] == num) count++;
else count--;
if (count == 0) {
num = numbers[i];
count = 1;
}
}
// Verifying
//count = 0;
//for (int i = 0; i < n; i++) {
// if (numbers[i] == num) count++;
//}
//if (count * 2 > n) return num;
//return 0;
if (count > 0) return num;
return 0;
}
int main() {
//vector<int> vt = { 1, 2, 3, 2, 4, 2, 5, 2, 3};
vector<int> vt = { 1, 2, 3, 5, 4, 2, 2, 2, 3 };
cout << MoreThanHalfNum_Solution(vt) << endl;
return 0;
}