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

两种方式：

1、定义一个新数组arr，遍历数组给arr赋值，arr[元素]=出现的次数

2.排序下arr,取第一个的key和value,key是目标元素，value是出现次数，验证下后返回

3.时间复杂度是O(n) 空间上会新创建个数组

1、定义变量e代表出现次数最多的元素，变量count用于判断出现次数用

2.遍历数组，当前元素与e比较，相同的count++,不同的count--,count为0时当前元素覆盖e

3.遍历数组验证e所出现的次数有没有超过一半

4.时间复杂度O(n) 空间复杂度O(n)

1. e,count=1 
2.  
3. for i=1;i<arr.length;i++ 
4.  
5.   if arr[i]==e 
6.  
7.     count++ 
8.  
9.   else 
10.  
11.     count-- 
12.  
13.   if count==0 
14.  
15.     e=arr[i] 
16.  
17.     count=1 
18.  
19. count=0 
20.  
21. for i=0;i<arr.length;i++ 
22.  
23.   if arr[i]==e 
24.  
25.     count++ 
26.  
27. if count*2>arr.length 
28.  
29.   return e 
30.  
31. <?php 
32.  
33. $arr=array(1,2,3,2,2,2,5,4,2); 
34.  
35. $e=MoreThanHalfNum_Solution($arr); 
36.  
37. var_dump($e); 
38.  
39.    
40.  
41. function MoreThanHalfNum_Solution($numbers){ 
42.  
43.     $arr=$numbers; 
44.  
45.     $e=$arr[0]; 
46.  
47.     $count=1; 
48.  
49.     $length=count($arr); 
50.  
51.     for($i=1;$i<$length;$i++){ 
52.  
53.         if($arr[$i]==$e){ 
54.  
55.             $count++; 
56.  
57.         }else{ 
58.  
59.             $count--; 
60.  
61.         }   
62.  
63.    
64.  
65.         if($count==0){ 
66.  
67.             $e=$arr[$i]; 
68.  
69.             $count=1; 
70.  
71.         }   
72.  
73.     }   
74.  
75.     $count=0; 
76.  
77.     for($i=0;$i<$length;$i++){ 
78.  
79.         if($arr[$i]==$e){ 
80.  
81.             $count++; 
82.  
83.         }   
84.  
85.     }   
86.  
87.     if($count*2>$length){ 
88.  
89.         return $e;  
90.  
91.     }   
92.  
93.     return 0; 
94. }

Tags: php数组次数 php数字统计

分享到：