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)
e,count=1 for i=1;i<arr.length;i++ if arr[i]==e count++ else count-- if count==0 e=arr[i] count=1 count=0 for i=0;i<arr.length;i++ if arr[i]==e count++ if count*2>arr.length return e
<?php $arr=array(1,2,3,2,2,2,5,4,2); $e=MoreThanHalfNum_Solution($arr); var_dump($e); function MoreThanHalfNum_Solution($numbers){ $arr=$numbers; $e=$arr[0]; $count=1; $length=count($arr); for($i=1;$i<$length;$i++){ if($arr[$i]==$e){ $count++; }else{ $count--; } if($count==0){ $e=$arr[$i]; $count=1; } } $count=0; for($i=0;$i<$length;$i++){ if($arr[$i]==$e){ $count++; } } if($count*2>$length){ return $e; } return 0; }
以上就是本次的全部内容和代码,感谢大家对我们的支持。
相关推荐
-
PHP实现统计一个数字在排序数组中出现次数的方法
本文实例讲述了PHP实现统计一个数字在排序数组中出现次数的方法.分享给大家供大家参考,具体如下: 题目 统计一个数字在排序数组中出现的次数. 题解 既然是排序数组,使用二分查找是效率最高的.找到之后再向两侧拓展一下. 代码 <?php function GetNumberOfK($data, $k) { if(count($data)==0){ return 0; } $index = 0; $low = 0; $high = count($data)-1; $middle = 0; //二分查
-
PHP统计数值数组中出现频率最多的10个数字的方法
本文实例讲述了PHP统计数值数组中出现频率最多的10个数字的方法.分享给大家供大家参考.具体分析如下: 该问题属于TOPK范畴,统计单词出现频率,做报表,数据统计的时会常用! php代码如下: //随机生成数值数组 for($i=0;$i<1000;$i++){ $ary[]=rand(1,1000); } //统计数组中所有的值出现的次数 $ary=array_count_values($ary); arsort($ary);//倒序排序 $i=1; foreach($ary as $key=
-
php实现数组重复数字统计实例
在一个长度为n的数组里的所有数字都在0到n-1的范围内. 数组中某些数字是重复的,但不知道有几个数字是重复的.也不知道每个数字重复几次.请找出数组中任意一个重复的数字. 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2. 1.哈希法 2.定义备用数组,作为哈希使用,key是原数组每个元素 value是出现的次数 3.遍历哈希数组 hash for i=0i;<arr.length;i++ hash[arr[i]]++; foreach hash as
-
PHP源代码数组统计count分析
zend给php的所有变量都用结构的方式去保存,而字符串的保存和数组的保存也是不同的,数组采用的是hash表的方式去保存(大家知道hash保存的地址有效的减少冲突-hash散列表的概念你懂的),而在php中的结构体上表现如下: 复制代码 代码如下: //文件1:zend/zend.h /* * zval */ typedef struct _zval_struct zval; ... typedef union _zvalue_value { long lval; /* long value *
-
php数组函数序列 之array_count_values() 统计数组中所有值出现的次数函数
array_count_values()定义和用法 array_count_values() 函数用于统计数组中所有值出现的次数. 本函数返回一个数组,其元素的键名是原数组的值,键值是该值在原数组中出现的次数. 语法 array_count_values(array) 参数 描述 array 必需.规定输入的数组. 例子 复制代码 代码如下: <?php $a=array("Cat","Dog","Horse","Dog"
-
php统计数组元素个数的方法
count():对数组中的元素个数进行统计; sizeof():和count()具有同样的用途,这两个函数都可以返回数组元素个数.可以得到一个常规标量变量中的元素个数,如果传递给这个函数的数组是一个空数组,或者是一个没有经过设定的变量,返回的数组元素个数就是0; array_count_value():统计每个特定的值在数组$array中出现过的次数; 如: $array=array(4,5,1,2,3,1,2,1); $ac=array_count_value($array); 将创建一个名为
-
PHP统计二维数组元素个数的方法
解决思路1. 首先从数据库的congtent字段读取数据,并把它们合并成一个字符串. 复制代码 代码如下: <?php while($myrow = $connector -> fetch_array($result)) { //$r[] = explode(",", $myrow["content"]); $str .= $myrow["content"].','; } $arr_str = substr($str, 0, -1
-
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代表出现次数最多的元素,变量coun
-
基于Java代码实现数字在数组中出现次数超过一半
下文通过几种方法给大家介绍java数组数字出现次数,具体内容如下所示: 方法一: 数组排序,然后中间值肯定是要查找的值. 排序最小的时间复杂度(快速排序)O(NlogN),加上遍历. 方法二: 使用散列表的方式,也就是统计每个数组出现的次数,输出出现次数大于数组长度的数字. 方法三: 出现的次数超过数组长度的一半,表明这个数字出现的次数比其他数出现的次数的总和还多. 考虑每次删除两个不同的数,那么在剩下的数中,出现的次数仍然超过总数的一般,不断重复该过程,排除掉其他的数,最终找到那个出现次数超过
-
PHP实现找出数组中出现次数超过数组长度一半的数字算法示例
本文实例讲述了PHP实现找出数组中出现次数超过数组长度一半的数字算法.分享给大家供大家参考,具体如下: <?php * 算法要求:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字. * * 算法分析:我们需要计算数组中每个数字的出现次数.在PHP中我们可以使用in_array函数 * 来判断一个元素是否出现在数组中.比如数组中含有1,2,3三个元素,我们要判断1是否存在 * 可以使用in_array(1,$array)来判断,但是这样只能判断1出现了一次,因为对于含有数组 * 元素1
-
JS获取数组中出现次数最多及第二多元素的方法
本文实例讲述了JS获取数组中出现次数最多及第二多元素的方法.分享给大家供大家参考,具体如下: 整型数组中出现次数最多和第二多的元素 用哈希数组 function f(arr){ var i; var length=arr.length; var hash=[];//使用哈希数组 for(i=0;i<length;i++){ if(!hash[arr[i]])hash[arr[i]]=1;//没有初始化的数组元素为undefined,undefined++为NaN else hash[arr[i]
-
php实现数组中索引关联数据转换成json对象的方法
本文实例讲述了php实现数组中索引关联数据转换成json对象的方法.分享给大家供大家参考.具体实现方法如下: public static function encode(&$var) { return '{'.implode(',',self::encodeExcute($var)).'}'; } private static function encodeExcute(&$var) { $json = array(); switch (gettype($var)) { case 'arr
-
php从数组中随机选择若干不重复元素的方法
本文实例讲述了php从数组中随机选择若干不重复元素的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* * $array = the array to be filtered * $total = the maximum number of items to return * $unique = whether or not to remove duplicates before getting a random list */ function un
-
JavaScript实现将数组中所有元素连接成一个字符串的方法
本文实例讲述了JavaScript实现将数组中所有元素连接成一个字符串的方法.分享给大家供大家参考.具体如下: 下面的代码演示了JS中如何通过数组对象的join方法将数组元素连接成一个字符串输出 <!DOCTYPE html> <html> <body> <p id="demo"> Click the button to join the array elements into a string. </p> <butto
-
C++算法之在无序数组中选择第k小个数的实现方法
本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法.分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数.这里数组可以是有重复的值! 下面是自己写的一个函数,记在此处来记忆我留下的痕迹! //选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,in
-
Java中高效判断数组中是否包含某个元素的几种方法
目录 检查数组是否包含某个值的方法 使用List 使用Set 使用循环判断 使用Arrays.binarySearch() 时间复杂度 使用一个长度为1k的数组 使用一个长度为10k的数组 总结 补充 使用ArrayUtils 完整测试代码 长字符串数据 如何检查一个数组(无序)是否包含一个特定的值?这是一个在Java中经常用到的并且非常有用的操作.同时,这个问题在Stack Overflow中也是一个非常热门的问题.在投票比较高的几个答案中给出了几种不同的方法,但是他们的时间复杂度也是各不相同
随机推荐
- ASP.NET Core中使用xUnit进行单元测试
- VBS实现截图功能
- Python使用sftp实现上传和下载功能(实例代码)
- vue开发心得和技巧分享
- 使用paramiko远程执行命令、下发文件的实例
- 有关于PHP中常见数据类型的汇总分享
- ASP:ActiveX不能创建Scripting.FileSystemObject对象解决办法
- Android开发悬浮按钮 Floating ActionButton的实现方法
- PHP使用mysql_fetch_object从查询结果中获取对象集的方法
- ECMA5数组的新增方法有哪些及forEach()模仿实现
- PowerShell数组的一些操作技巧
- jquery 事件执行检测代码
- Android 编辑头像功能简单实现实例(图片选取,裁剪)
- java字符串抉择
- C#实现根据字节数截取字符串并加上省略号的方法
- PHP的error_reporting错误级别变量对照表
- PHP实现加密文本文件并限制特定页面的存取的效果
- angularjs 页面自适应高度的方法
- InvocationHandler中invoke()方法的调用问题分析
- ThinkPHP防止重复提交表单的方法实例分析