|
题目：数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过了数组长度的一半，因此输出2.
#include <stdio.h>
#include <stdlib.h>
int check_more_than_one_half(int array[],int len,int value)
{
int i;
int times = 0;
for(i = 0; i < len; i++) {
if(array[i] == value)
times++;
}
if(times >= len/2)
return 0;
return -1;
}
int get_more_than_one_half(int array[],int len)
{
int times;
int value;
int *p_start, *p_end;
if(len < 0) {
printf("error: on array elements\n");
return -1;
}
value = array[0];
times = 1;
p_start = &array[1];
p_end = &array[len-1];
while(p_start <= p_end) {
if(value == *p_start) {
times++;
}else {
times--;
if(times == 0) {
p_start++;
value = *p_start;
times=1;
}
}
p_start++;
}
if(times < 0) {
printf("no one element whose number is more than one half array number\n");
return -1;
}
if(check_more_than_one_half(array,len,value) == 0)
printf("%d is more than one half\n",value);
else
printf("no one element whose number is more than one half array number\n");
return value;
}
int main()
{
int a[] = {1,2,3,2,2,2,5,4,2};
(void)get_more_than_one_half(a,sizeof(a)/sizeof(a[0]));
return 0;
}
| 
转播
