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;

}

以上就是本次的全部内容和代码,感谢大家对我们的支持。

(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中也是一个非常热门的问题.在投票比较高的几个答案中给出了几种不同的方法,但是他们的时间复杂度也是各不相同

随机推荐