# 《剑指offer》数组中出现次数超过数组长度一半的数字

2018-02-02 08:28:10来源:cnblogs.com作者:你好，bigshot人点击

` 1 int MoreThanHalfNum_Solution(int *arr,int len)  2 { 3     int i,j,flag = 1,count = 1; 4     for (i=0; i<len-1; i++)  //给数组排序 5     { 6         for (j=0; j<len-1-i; j++) 7         { 8             if (arr[j]>arr[j+1]) 9             {10                 int tmp = arr[j];11                 arr[j] = arr[j+1];12                 arr[j+1] = tmp;13                 flag = 0;14             }15         }16         if (flag)17             break;18     }19     for (i = 0; i<len; i++) //遍历一遍查找是否有符合题意的数字20     {21         if (arr[i] == arr[i+1])22         {23             j = i;24             count++;25             if (count>(len>>1)) 26             {27                 return arr[j];28             }29         }30         else31         {32             count = 1;33         }34     }35     return 0;36 }`

` 1  int MoreThanHalfNum_Solution(int *arr,int len)  2   { 3       int i = 1; 4       int k = 0; 5       int count = 1; 6       while (i<len) 7       { 8           if (arr[i]==arr[k])  9           {10               k = i; //记录当前位置11               count++;12           }13           else14           {15               count--;//不同则计数器减116               if (count == 0)17               {18                   count = 1;19                   k = i;20               }21           }22           i++;23       }24       if (count)25       {26           count = 0;27           for (i=0; i<len; i++)28           {29               if(arr[k]==arr[i])30                   count++;31           }32           if (count>len/2)33               return arr[k];34           else35               return 0;36       }37       else38           return 0;39   }`

CSDN博客地址：http://blog.csdn.net/qq_38646470