剑指Offer——面试题29:数组中出现次数超过一半的数字

时间:2022-12-01 11:02:34

数组中出现次数超过一半的数字


题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为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;
}