题目：找出数组中出现次数超过一半的元素
解法：每次删除数组中两个不同的元素，删除后，要查找的那个元素的个数仍然超过删除后的元素总数的一半
#include <stdio.h> int half_number(int a[], int n)
{
if( a == NULL || n <= )
return -; int i, candidate;
int times = ;
for( i=; i<n; i++ )
{
if( times == )
{
candidate = a[i];
times = ;
}
else if( a[i] == candidate )
++times;
else
--times;
}
return candidate;
} int main(void)
{
int a[] = {,,,,,,,,}; int result = half_number(a, );
if( result != - )
printf("%d\n", result);
else
printf("Error.\n"); return ;
}
该题的扩展：数组中有3个元素出现的次数都超过数组元素总数N的1/4, 找出这三个元素
解法：同上，但是每次删除4个互不相同的元素，处理上比上面的稍微麻烦
#include <stdio.h> void find(int a[], int n)
{
if( a==NULL || n<= )
{
printf("Error.\n");
return ;
} int i,j;
int times[] = {,,}; // 3个candidate的计数
int candidate[] = {-,-,-}; // 假设元素不可能是-1 for( i=; i<n; i++ )
{
if( times[] == && a[i] != candidate[] && a[i] != candidate[] ) // 第1个candidate目前空缺, 且当前元素a[i]不等于其他两个candidate时, 将该元素作为新的candidate
{
candidate[] = a[i];
times[] = ;
}
if( times[] == && a[i] != candidate[] && a[i] != candidate[] )
{
candidate[] = a[i];
times[] = ;
}
if( times[] == && a[i] != candidate[] && a[i] != candidate[] )
{
candidate[] = a[i];
times[] = ;
}
else if( a[i] == candidate[] )
{
++times[];
}
else if( a[i] == candidate[] )
{
++times[];
}
else if( a[i] == candidate[] )
{
++times[];
}
else // 删除4个各不相同的数组元素, 删除后
{
--times[];
--times[];
--times[];
}
}
printf("%d %d %d\n",candidate[],candidate[],candidate[]);
} int main(void)
{
int a[] = {,,,,,,,,,,,,,,,,,,,,,,};
find(a, );
return ;
}
