学步园

74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：这是一道广为流传的面试题，包括百度、微软和 Google  在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。

/*
74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：这是一道广为流传的面试题，包括百度、微软和 Google  在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。

方法1： 
记住是一个 找最大出现次数即可 逐个向后 遇相同加 不同减 最后就是最大的出现次数 
方法2：利用哈希表或者数组统计每个字符出现的次数，然后从里面找到出现次数超过一半的
方法3：排序后，取数组的中间元素，因为次数超过一半 
*/
#include<iostream>
#include<stdio.h>
#include<map>
#include<string.h>
#include<algorithm> 
using namespace std;

char getMajor1(char a[]) 
{
	int cnt=0,n;
	char x;
	n=strlen(a);
	for(int i=0;i<n;i++)
	{
		if(cnt==0)//cnt=0表示前面数字出现相同 
		{ 
			x=a[i];
			cnt++;
		}
	 	else if(a[i]==x)
			cnt++;
		else  
			cnt--;   
	}
	return x;
}

char getMajor2(char a[])
{  
	map<char,int> m;  
    map<char,int>::iterator it ;
	int n; 
    n=strlen(a);  
    for(int i=0;i<n;i++)  
    {  
        it=m.find(a[i]);  
        if(it!=m.end())   
            m[a[i]]++;  
		else
            m[a[i]]=1;  
    }  
  
    it=m.begin();  
    while(it!=m.end())  
    {  
        if((*it).second>n/2)  
            return (*it).first;  
        it++;  
    }  
    return -1;  
}  
  
char getMajor3(char a[])//排序后取中间元素  
{  
	int len=strlen(a);
    sort(a,a+len);  
    return a[len/2];  
}  

int main()
{
	char str[100]; 
	while(scanf("%s",str))
	{
		cout<<str<<":超过出现次数超过一半的数字是："<<endl;
		cout<<"方法1："<<getMajor1(str)<<endl;
		cout<<"方法2："<<getMajor2(str)<<endl;
		cout<<"方法3："<<getMajor3(str)<<endl;
	}
	return 0;
}
/*
123121211
111
1212122
123222542
*/