[PHP] 算法-数组中出现次数超过一半的数字的PHP实现
2023-02-18 15:41:46 时间
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为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; }
相关文章
- [MySQL] 解决Error 1698: Access denied for user 'root'@'localhost'
- [日常] 前端资源测试机上忽略版本号的的nginx配置
- [PHP] PHP PDO与mysql的连接单例防止超时情况处理
- [PHP] 使用Socket提供Http服务
- [PHP] 实现路由映射到指定控制器
- [PHP] 命令行执行整合pathinfo模拟定时任务
- [PHP] 自定义错误处理
- [Php] windows下使用composer出现SHA384 is not supported by your openssl extension
- [PHP] url的pathinfo模式加载不同控制器的实现
- [PHP] 自动加载的实现
- [PHP] 新版本PHP7.4与新版本MySQL8认证问题
- [PHP] PHP请求Socket接口测试
- [PHP] error_reporting(0)可以屏蔽Fatal error错误
- [PHP] 读取大文件并显示
- [PHP] PDO对象与mysql的连接超时
- [PHP] time_wait与长连接短连接
- [PHP] Ubuntu快速安装起PHP7.4
- [PHP] CentOS下搭建下PHP的运行环境
- [日常] 修复了grub引导问题
- [MySQL] docker下安装使用mysql配置主从复制