面试题29

题目描述：

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

输入：

每个测试案例包括2行：

第一行输入一个整数n（1<=n<=100000），表示数组中元素的个数。

第二行输入n个整数，表示数组中的每个元素，这n个整数的范围是[1,1000000000]。

输出：

对应每个测试案例，输出出现的次数超过数组长度的一半的数，如果没有输出-1。

样例输入：

9 1 2 3 2 2 2 5 4 2

样例输出：

2

思路：根据题意，要找到数字个数超过总个数的一般的数值。那么我们可以想到如果这些数据是排序的，并且存在这样一个数，那么是不是这个数字的中值一定就是这个数（好好理解下）

解法一：根据上面思路，并且假设输入数据的值可以改变。那么利用快排，将数组排序（剑指offer上讲的解法一，我的理解就是单纯快排，根据这种方法。但是自己手写的partition函数，最后一组T了，据说算导上具体写了）。时间复杂度为O（n*logn）。再通过一次遍历，判断是否存在满足条件的数字，时间复杂度为O（n)。所以这种方法的总的时间复杂度为O（n*logn + n） ==O（n);

解法二：可以参照上面的思路（但不是找中值).根据题意，找一个数值个数超过总数一半的数。那么就意味着其他数据的个数总和就小于这个数的个数。由此，我们就只需要采用二进制数1，0.用来表示，是或不是该数。因此我们利用两个变量pos和sum。分别表示当前pos数据，和当前pos数据的个数。从头到尾遍历一遍。当遍历的数值等于当前数据pos时，那么当前数据的个数sum+1;否则sum-1;如果这个数据的个数为0.就把遍历位置的数据存入当前pos数据，并且使sum=1；按照这种思路遍历到最后一个数据，就能得出满足题意得值。时间复杂度为O（n）。最后在遍历一个，检验数据。总的时间复杂度为O（2*n）==O(n );

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;

const int MAX = 100005;
int num[MAX ], temp[ MAX ];

int CheckInvalidArray(int *num, int length){
	if (num == NULL ?? length <= 0)
		return true;
	return false;
}
int CheckMoreThanHalf(int *num, int length, int pos){
	int sum = 0;
	for (int i = 0; i < length; ++i){
		if (num[i] == pos)
			sum++;
	}
	if (2 * sum <= length)
		return false;
	return true;
}

int main(){
	int n;
	while (cin >> n){
		for (int i = 0; i < n; ++i)
			cin >> num[i];
		if (CheckInvalidArray(num, n))
			return 0;
		int sum = 0;
		int pos = num[0];
		for (int i = 1; i < n; ++i){
			if (sum == 0){
				sum = 1;
				pos = num[i];
			}
			if (pos == num[i]){
				sum++;
			}
			else
				sum--;
		}
		if (!CheckMoreThanHalf(num, n, pos))
			pos = 0;
		if (pos)
			cout << pos << endl;
		else
			puts("-1");
	}
	return 0;
}