数组中出现次数超过一半的数字
题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
输入:{1,2,3,2,2,2,5,4,2}
输出:2
思路:1、针对本道题的特点,用一次遍历即时间复杂度为O(n),空间复杂度为O(1)
2、因为数组中某个数字出现的次数超过了数组长度的一半
3、也就是该数字最少出现 n/2 + 1 次,换句话说该数字出现次数比其它剩下的所有数字出现的次数都多
4、利用这个特点,我们从头开始遍历时,就把第一个数字a[0],创建2个变量:一个是数字,一个是该数字出现的次数,初始化为1;
5、如果a[1]与a[0]相同,则设为再加1(即2),如果a[1]与a[0]不同,则减1,如果该数字出现的次数已经为0,那么把数字替换成后面的那个,并且把次数重新赋值为1。
/* 题目:数组中出现次数超过一半的数字 */
#include<iostream>
#include<vector>
using namespace std;
bool checkArray(vector<int> number, int num){
int time = 0;
for (int i = 0; i < number.size(); i++){
if (number[i] == num){
time++;
}
}
if (time * 2>number.size()){
return true;
}
else{
return false;
}
}
int findNumber(vector<int> number){
//num表示某个数字,numTime表示某个数字出现的时间
int num;
int numTime;
num = number[0];
numTime = 1;
for (int i = 1; i < number.size(); i++){
if (numTime == 0){
num = number[i];
numTime++;
}
else if (num == number[i]){
numTime++;
}
else{
numTime--;
}
}
//这里判断输入的数组是否符合要求,即输入的数组中,是否存在某个元素出现的次数超过数组的长度的一半
if (checkArray(number, num)){
return num;
}
return 0;
}
int main(){
vector<int> number;
int temp;
//出现的次数
int occurrenceNumber;
do{
cin >> temp;
number.push_back(temp);
} while (cin.get() != '\n');
occurrenceNumber = findNumber(number);
cout << occurrenceNumber;
system("pause");
return 0;
}