VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > PHP >
  • php实现数组中出现次数超过一半的数字的统计方法

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字,例如输入一个长度为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. }
  95.  

出处:http://www.phpfensi.com/php/20211031/18312.html


相关教程