/*

题目：

    数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

    例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

*/

/*

思路：

    数组中出现次数超过数组长度的一半的值为target，

	则从头到尾遍历数组，遇到不同的值-1，遇到相同的值次数＋1，

	最终剩下的数字就可能是target，

	验证其出现次数是否超过数组长度的一半。

*/

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<set>

#include<vector>

using namespace std;

bool isTarget(vector<int> &numbers,int targetValue){

    int times = 0;

    for(int i = 0; i < numbers.size(); i++){

        if(numbers[i] == targetValue){

            times++;

        }

    }

    if(times*2 > numbers.size()){

        return true;

    }else{

        return false;

    }

}

int MoreThanHalfNum_Solution(vector<int> numbers) {

   if(numbers.size() == 0) return 0;

   int target = numbers[0];

   int myCount = 1;

   for(int i = 1; i < numbers.size(); i++){

        if(myCount == 0){

            target = numbers[i];

            myCount = 1;

        }else if(target == numbers[i]){

            myCount++;

        }else{

            myCount--;

        }

   }

   if(isTarget(numbers,target)){

        return target;

   }else{

    return 0;

   }

}

int main(){

    vector<int> a = {4,2,1,4,4,4};

    cout<<MoreThanHalfNum_Solution(a)<<endl;

}