当前位置:Gxlcms > PHP教程 > php如何实现数组中出现次数超过一半的数字的统计方法(代码)

php如何实现数组中出现次数超过一半的数字的统计方法(代码)

时间:2021-07-01 10:21:17 帮助过:2人阅读

本篇文章给大家带来的内容是关于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如何实现数组中出现次数超过一半的数字的统计方法(代码)的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行