整型数组处置算法（十）给定数组a[n]，其中有超过一半的数为一个定值，找出这个数。[2014人人网笔试题]

整型数组处理算法（十）给定数组a[n]，其中有超过一半的数为一个定值，找出这个数。[2014人人网笔试题]

原链接是：

人人网2013笔试算法题汇总

2.给定有n个数的数组a，其中有超过一半的数为一个定值，在不进行排序，不开设额外数组的情况下，以最高效的算法找出这个数。

int find(int* a, int n);

这道题的算法还可以优化一下,那就是对于这种情况：3,3,3,3,3,3,4,4,4,4。因为个数是10个，当统计的个数大于一半，那就可以中止判断了。实现如下：

int find(int *a, int n)    
{    
    int t = a[0];    
    int count = 0;    
    for (int i=0; i<n; ++i)    
    {    
        if (count == 0)    
        {    
            t = a[i];    
            count = 1;    
            continue;    
        }    
        else    
        {    
            if (a[i] == t)    
            {    
                count++;    
            }    
            else    
            {    
                count--;    
            }   
			
			//增加一个判断
			if (count > n/2)
			{
				return t;
			}
        }    
    }    
    
    return t;    
} 

这样的话，

Time Complexity: O(n/2)

Space Complexity:O(1)

另外一个实现方法：

int find1(int *a, int n) 
{
	int nTotal=0;
	int i;
	int j;
	int nMax=a[0];//最大值
	int nAvg;//平均值
	int nCount;

	for (i=0; i< n; i++)
	{
		nTotal += a[i];

		if (a[i]>nMax)
		{
			nMax = a[i];
		}
	}
	
	nAvg = nTotal/n;

	for (j=nAvg; j<=nMax; j++)
	{
		nCount = 0;
		for (i=0; i< n; i++)
		{
			if (a[i] == j)
			{
				nCount++;
			}

			if (nCount > n/2)
			{
				return j;
			}
		}

	}

	return 0;
}

测试代码：

int main()    
{    
    int n = 11;    
    //int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};    
	//int a[10] = {4, 3, 4, 3, 4, 3, 4, 3,3,3}; 
	int a[11] = {3, 3, 3, 4, 4, 4, 4, 4,3,3,3}; 

	//int a[10] = {3, 10, 10, 10, 10, 10, 10, 3, 3, 3}; 
    
    cout<<find1(a, n)<<endl;   
	
	cout<<find(a, n)<<endl;
    
    system("pause");    
    return 0;    
} 

测试结果就不贴了，有兴趣的朋友试试看。

转载请注明原创链接：http://blog.****.net/wujunokay/article/details/12227851