题目描述：

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

 

输入：

每个测试案例包括2行：

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

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

 

输出：

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

 

样例输入：

91 2 3 2 2 2 5 4 2

样例输出：

2

 1 #include <stdio.h> 2 void main() 3 { 4     int n; 5     while(scanf("%d",&n)!=EOF) 6     { 7         int array[100000]; 8         for (int i=0; i< n; i++) 9         {10             scanf("%d",&array[i]);11         }12         int result = array[0];13         int times = 1;14         i = 0;15         while(i < n)16         {17             if (times == 0)18             {19                 result = array[i];20                 times = 1;21             }22             if (result == array[i])23                 times++;24             else25                 times--;26             i++;27         }28         int count =0;29         for (int j=0; j < n; j++)30         {31             if(array[j]  == result)32                 count++;33         }34         if (2*count > n)35             printf("%d\n",result);36         else37             printf("-1\n");38     }39 }

another methord

 1 #include <stdio.h> 2  3 int partition(int array[], int start, int end) 4 { 5     int key = array[start]; 6     while(start < end) 7     { 8         while(start<end && array[end]>=key) end--; 9         if (start<end)10         {11             array[start] = array[end];12             start++;13         }14         else15         {16             break;17         }18 19         while(start <end && array[start] < key) start++;20         if (start < end)21         {22             array[end] = array[start];23             end--;24         }25     }26     array[start] = key;27     return start;28 }29 30 int checkMoreHalf(int array[],int lenght,int number)31 {32     int total = 0;33     for (int i=0; i<lenght; i++)34     {35         if (array[i] == number)36             total++;37     }38     if (2*total > lenght)39     {40         return 1;41     }42     return -1;43 }44 45 void MoreThanHalfNum(int array[], int length)46 {47     int middle = length >> 1;48     int start  = 0;49     int end    = length -1;50     int index = partition(array,start,end);51     while(index != middle)52     {53         if (index > middle)54         {55             end = index -1;56         }57         else58         {59             start = index+1;60         }61         index = partition(array,start,end);62     }63     if (checkMoreHalf(array,length,array[index]) == 1)64     {65         printf("%d\n",array[index]);66     }67     else68     {69         printf("-1\n");70     }71 }72 73 void main()74 {75     int n;76     while(scanf("%d",&n)!=EOF)77     {78         int array[100000];79         for (int i=0; i< n; i++)80         {81             scanf("%d",&array[i]);82         }83         MoreThanHalfNum(array,n);84     }85 }

 

数组中出现次数超过一半的数字