当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > 《剑指offer》数组中出现次数超过数组长度一半的

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

文章作者:新注册送38元体验金编程 上传时间:2019-08-22

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

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

新注册送38元体验金,方法一代码:

 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         else
31         {
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           else
14           {
15               count--;//不同则计数器减1
16               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           else
35               return 0;
36       }
37       else
38           return 0;
39   }

CSDN博客地址:

 

题目: 数组中有一个数字出现的次数超过数组长度的一半,请找...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:《剑指offer》数组中出现次数超过数组长度一半的

关键词: