[PHP] 算法-数组中出现次数超过一半的数字的PHP实现
2023-02-18 15:47:20 时间
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为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; }
相关文章
- NLP: Text Neural Network (Part1: textRNN, textCNN)
- [NetWork] 局域网基本原理
- Redis实现朋友圈,微博等Feed流功能,实现Feed流微服务(代码实现)
- 下载速率提升40% ,《斗罗大陆:魂师对决》是如何做到的?
- 华为Awareness kit,您旅途路上的超智能管家
- Discovery直播 | 移动应用“通行证”——钥匙环,解锁管家式安全出行服务
- 教你在“狼人杀”中实现变声效果
- 技术与艺术的结合,HMS Core让手机主题趣味丛生
- 受众同步管理功能上线,让你的活动礼包发对人
- 分析服务助力产品运营
- 租房买房行业报告上线,为房产服务数字化转型添砖加瓦
- 放码来战!HMS Core线上Codelabs挑战赛正式开始
- 一图读懂DCI版权服务
- 【HMS Core 6.0全球上线】Toolkit,您的智能辅助编程好帮手
- 眼镜选款新方法,用AR+Scene技术实现3D虚拟试戴
- HDD成都站:HMS Core 6.0带来新可能,多元服务驱动产品价值提升
- Insights直播预告 | 多媒体管线服务,助您轻松进入“技术流”创新阵地
- 华为音频编辑服务带你一键伴奏分离!
- 【HMS Core 6.0全球上线】Network Kit全链路网络加速技术,应用无惧网络拥塞
- 华为分析X HUAWEI Ads,上线深度转化事件回传功能,让ROI 看得见!