- 题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
- 题目解析
这道题目如果数字不是很多的话，可以用计数排序的方法。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if (numbers.empty())
return 0;
unordered_map<int, int>map;
for (int i = 0; i < numbers.size(); i++){
map[numbers[i]]++;
}
int len = (numbers.size() >> 1);
for (auto &it : map){
if (it.second>len)
return it.first;
}
return 0;
}
};
这道题目trick太多了，这是另一种解法。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int size = numbers.size();
if (size == 0)
return 0;
int num = numbers[0], count = 1;
for (int i = 1; i < size; i++){
if (numbers[i] == num)
count++;
else count--;
if (count == 0){
num = numbers[i];
count = 1;
}
}
//验证
count = 0;
for (int i = 0; i < size; i++){
if (numbers[i] == num)
count++;
}
if (count * 2>size)
return num;
return 0;
}
};
还有一种解法，先对数组进行排序，然后判断numbers[i] == numbers[i+len/2]。醉了简直。
int len = numbers.size();
sort(numbers.begin(), numbers.end());
for (int i = 0; i < len;i++)
if (numbers[i] == numbers[i + len / 2])
return numbers[i];
return 0;