數組中出現次數超過一半的數字

數組中出現次數超過一半的數字

數組中有一個數字出現的次數超過數組長度的一半，找出這個數字。

思路：如果數組中一個數字出現的次數超過數組長度的一半，把這個數組排序，位於數組中間的數字一定是那個次數超過一半的數字。

參考代碼：

root@gt:/home/git/Code# ./a.out 2root@gt:/home/git/Code# cat morethanhalf.c #include <stdio.h>int check(int* parr,int len,int res){ int times = 0; for(int i = 0;i < len;++i) { if(parr[i] == res) ++times; } int ismore = 0; if(times >= len/2) ismore = 1; return ismore;}void exchange(int* pa,int* pb){ int temp = *pa; *pa = *pb; *pb = temp;}int partition(int* parr,int start,int end){ int index = parr[end]; int i = start - 1; int j = start; for(;j < end;++j) { if(parr[j] <= index) { ++i; exchange(&parr[i],&parr[j]); } } exchange(&parr[i + 1],&parr[j]); return i + 1;}int morethanhalf(int* parr,int len){ if(parr == NULL || len <= 0) return 0; int middle = len/2; int start = 0; int end = len - 1; int index = partition(parr,start,end); while(index != middle) { if(index > middle) { end = index - 1; index = partition(parr,start,end); } else { start = index + 1; index = partition(parr,start,end); } } int res = parr[middle]; if(!check(parr,len,res)) res = 0; return res;}int main(){ int parr[] = {1,2,3,2,2,2,5,4,2}; int res = morethanhalf(parr,sizeof(&parr)); printf("%d
",res); return 0;}

推薦閱讀：