php实现数组中出现次数超过一半的数字的统计方法

yipeiwu_com5年前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;

 

}

以上就是本次的全部内容和代码,感谢大家对【宜配屋www.yipeiwu.com】的支持。

相关文章

PHP调用QQ互联接口实现QQ登录网站功能示例

PHP调用QQ互联接口实现QQ登录网站功能示例

本文实例讲述了PHP调用QQ互联接口实现QQ登录网站功能。分享给大家供大家参考,具体如下: 调用QQ登录接口,首先要到QQ互联完善开发者认证信息,并通过审核,然后创建一个网站应用,获得A...

PHP开发之归档格式phar文件概念与用法详解【创建,使用,解包还原提取】

本文实例讲述了PHP开发之归档格式phar文件概念与用法。分享给大家供大家参考,具体如下: 一个php应用程序往往是由多个文件构成的,如果能把他们集中为一个文件来分发和运行是很方便的,这...

深入理解:单一入口、MVC、ORM、CURD、ActiveRecord概念

MVC MVC是一个设计模式,它强制性的使应用程序的输入、处理和输出分开。使用MVC应用程序被分成三个核心部件:模型(M)、视图(V)、控制器(C),它们各自处理自己的任务。 视图 :...

php获取CSS文件中图片地址并下载到本地的方法

本文实例讲述了php获取CSS文件中图片地址并下载到本地的方法。分享给大家供大家参考。 具体实现代码如下: 复制代码 代码如下: /**  * 获取CSS中图片地址,并且保存...

php将字符串随机分割成不同长度数组的方法

本文实例讲述了php将字符串随机分割成不同长度数组的方法。分享给大家供大家参考。具体分析如下: 这里使用php对字符串在指定的长度范围内进行随机分割,把分割后的结果存在数组里面 fu...