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

来源：转载 发布时间：2018-10-15 15:11:14 阅读量：656

本篇文章给大家带来的内容是关于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)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

<?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
分享：
评论：
你还没有登录，请先

热门标签

热门文章

    推荐文章