【剑指offer】出现次数超过一半的数字

转载请注明出处：http://blog.csdn.net/ns_code/article/details/26957383

题目描述：

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

    1、一个数字在数组中出现次数超过了一半，则排序后，位于数组中间的数字一定就是该出现次数超过了长度一半的数字（可以用反证法证明），也即是说，这个数字就是统计学上的中位数。最容易想到的办法是用快速排序对数组排序号后，直接取出中间的那个数字，这样的时间复杂度为O(nlogn)，空间复杂度为O(1)。

    2、事实上可以不用对数组进行排序，或者说仅部分排序，受快速排序的partition函数的启发，我们可以利用反复调用partition函数来求的该数字。我们现在数组中随机选取一个数字，而后通过Partition函数返回该数字在数组中的索引index，如果index刚好等于n/2，则这个数字便是数组的中位数，也即是要求的数，如果index大于n/2，则中位数肯定在index的左边，在左边继续寻找即可，反之在右边寻找。这样可以只在index的一边寻找，而不用两边都排序，减少了一半排序时间。这种情况的平均时间复杂度大致为：T(n) = n+n/2+n/4+n/8+....+1，很明显当n很大时，T(n)趋近于2n，也就是说平均情况下时间复杂度为O(n),但是这种情况下，最坏的时间复杂度依然为O(n*n)，最坏情况下，index总是位于数组的最左或最右边，这样时间复杂度为T(n) = n+n-1+n-2+n-3+....+1 = n(n-1)/2，显然，时间复杂度为O(n*n)，空间复杂度为O(1)。

    我用该方法写了下代码，并在九度OJ上run，报了超时，代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
bool IsExisted;

void Swap(int *a,int *b)
{
	if(*a != *b)
	{
		*a = *a + *b;
		*b = *a - *b;
		*a = *a - *b;
	}

}

/*
算法导论版快排的Partition函数
*/
int Partition(int *A,int low,int high)
{
	if(A==NULL || low<0 || high<0 || low>=high)
		return -1;
	
	int small = low-1;
	int j;
	for(j=low;j<high;j++)
	{
		if(A[j] <= A[high])
		{
			++small;
			if(j != small)
				Swap(&A[j],&A[small]);
		}
	}
	++small;
	Swap(&A[small],&A[high]);
	return small;
}

int Random_Partition(int *A,int low,int high)
{
	//设置随机种子
	srand((unsigned)time(0));
	int index = low + rand()%(high-low+1);
	Swap(&A[index],&A[high]);
	return Partition(A,low,high);
}


/*
判断关键字key在数组A中出现的次数是否超过一半
*/
bool IsMoreThanHalf(int *A,int len,int key)
{
	int times = 0;
	int i;
	for(i=0;i<len;i++)
		if(A[i] == key)
			times++;
	if(2*times <= len)
		return false;
	else
		return true;
}
 
/*
返回数组A中出现次数超过一半的数字
基于Partition函数的实现
*/
int MoreThanHalf(int *A,int len)
{
	if(A==NULL || len<1)
	{
		IsExisted = false;
		return -1;
	}

	int low = 0;
	int high = len-1;
	int mid = len>>1;
	int index = Random_Partition(A,low,high);
	while(index != mid)
	{
		if(index > mid)
			index = Random_Partition(A,low,index-1);
		else
			index = Random_Partition(A,index+1,high);
	}

	int key = A[mid];
	if(!IsMoreThanHalf(A,len,key))
	{
		IsExisted = false;
		return -1;
	}
	return key;
}

int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		int *A = (int *)malloc(sizeof(int)*n);
		if(A == NULL)
			exit(EXIT_FAILURE);

		int i;
		for(i=0;i<n;i++)
			scanf("%d",A+i);

		IsExisted = true;
		int key = MoreThanHalf(A,n);
		if(IsExisted)
			printf("%d\n",key);
		else
			printf("-1\n");
	}
	return 0;
}

    算法导论第九章上给出了一种基于Partition的在最坏情况下也能以O(n)运行的选择第k小的数字的方法（选择中位数是选择地k小元素的特殊情况，这里k=n/2），这种方法能够保证选择的枢轴元素在中位数的附近，算法导论上并给出了详细的证明，证明该方法在最坏情况下的时间复杂度也为O(n)。

在修改划分算法后，我们通过以下步骤来实现在n个元素的数组中找第i小元素的SELECT：
１、把数组A分成ceiling(n/5)个组，除最后一组外，每组都有5个元素，最后一组有n mod 5个元素；
２、对每组（的五个元素）用插入法进行排序，然后选出该组的中位数，即排好序的第三个元素；
３、对于步骤2中得到的所有的中位数，通过递归调用SELECT来找到它们的（下）中位数x，（也就是找到第2步得到的所有中位数中第floor(ceiling(n/5) / 2)小个元素）；
４、利用修改后的划分算法把元素分成小于x和大于x的两个子数组。如果设k为划分低区的元素个数加一，则x就是A中第k小的元素；
５、如果i = k，那我们就返回x，它便是我们要找的值。如果i < k，我们就在第4步里的划分低区继续递归调用SELECT来找到第i小的元素；如果i > k，我们就在划分高区递归调用SELECT找第i-k小的数。

    需要注意的是，算法中每个分组大小为5，如果改成3是不行的（每组为3的时间复杂度为O(NlgN）。如果分成组数为奇数的话，每组大小要>=5才能保证O(N)的时间。

    3、考虑用哈希，key保存数组元素，value保存出现的次数，这样在遍历O(n)能做出key-value的映射，再用O(k)(k为需要的槽的个数)可以找出出现次数超过一半的key，但是由于数组中元素的大小范围未知，因此使用这种方法，首先不能确定哈希表的大小，即使通过遍历一次求得了最大值，范围很大的话，又要花费很大心思设计很好的哈希函数来完成key-value的映射，且不具有通用性，而且还要考虑数组中元素为负值的情况，因此用哈希表不合适。

    4、网上很流行的做法，由于该数字的出现次数比所有其他数字出现次数的和还要多，因此可以考虑在遍历数组时保存两个值：一个是数组中的一个数字，一个是次数，。当遍历到下一个数字时，如果下一个数字与之前保存的数字相同，则次数加1，如果不同，则次数减1，如果次数为0，则需要保存下一个数字，并把次数设定为1。由于我们要找的数字出现的次数比其他所有数字的出现次数之和还要大，则要找的数字肯定是组后一次把次数设为1时对应的数字。该方法的时间复杂度为O(n)，空间复杂度为O(1)。

    用该思路写出的代码AC，如下：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
bool IsExisted;

/*
判断关键字key在数组A中出现的次数是否超过一半
*/
bool IsMoreThanHalf(int *A,int len,int key)
{
	int times = 0;
	int i;
	for(i=0;i<len;i++)
		if(A[i] == key)
			times++;
	if(2*times <= len)
		return false;
	else
		return true;
}

/*
找出出现次数超过一半的数字
*/
int MoreThanHalfDP(int *A,int len)
{
	if(A==NULL || len<1)
	{
		IsExisted = false;
		return -1;
	}
	
	int result = A[0];
	int times = 1;
	int i;
	for(i=1;i<len;++i)
	{
		if(times == 0)
		{
			result = A[i];
			times = 1;
		}
		else if(A[i] == result)
			++times;
		else
			--times;
	}
	if(!IsMoreThanHalf(A,len,result))
	{
		IsExisted = false;
		return -1;
	}
	return result;
}

int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		int *A = (int *)malloc(sizeof(int)*n);
		if(A == NULL)
			exit(EXIT_FAILURE);

		int i;
		for(i=0;i<n;i++)
			scanf("%d",A+i);

		IsExisted = true;
		int key = MoreThanHalfDP(A,n);
		if(IsExisted)
			printf("%d\n",key);
		else
			printf("-1\n");
	}
	return 0;
}