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

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

分享
第七城市

题目: 
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 
解析: 
看到这道题我首先想到先给数组排序,在遍历一遍查找已经排好序的数组中的符合题意的数。这种方法是可行的,但是这种方法太明显了,而且排序时间复杂度大于O(n),感觉面试官肯定不会同意。于是我想到了用第i个数与i+1个数进行比较,如果相同则记下此数并且计数器加一,不同就减一,当计数器为零时,重新记下这个数;一遍遍历完毕,如果计数器为零则没有这样的数,否则有可能存在,再遍历一遍,将记录的数字与数组所有数字比较,最后如果相同的数字大于数组长度一般则返回该数,反之返回0,这种方法的时间复杂度为O(n); 
下面我把两种方法的代码都写下来了分享给大家。

方法一代码:

 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

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台