文档章节

php如何实现统计一个数字在排序数组中出现的次数(代码)

o
 osc_fmg49rzg
发布于 2019/03/20 14:13
字数 274
阅读 18
收藏 0
php

精选30+云产品,助力企业轻松上云!>>>

统计一个数字在排序数组中出现的次数。

博客 www.51msk.cn


1.有序的数组查找,使用二分法
2.二分法查找第一次出现的位置,二分法查找最后一次出现的位置,end - start +1

 

left=getLeft(data,k)

right=getRight(data,k)

retun right-left+1

getLeft data,k

    left=0

    right=arr.length-1

    mid=left+(right-left)/2

    while  left<=right

        if arr[mid]<k    //关键

            left=mid+1

        else

            right=mid-1

        mid=left+(right-left)/2

    return left

getRight data,k

    left=0

    right=arr.length-1

    mid=left+(right-left)/2

    while  left<=right

        if arr[mid]<=k   //关键

            left=mid+1

        else

            right=mid-1

        mid=left+(right-left)/2

    return right







































<?php

function GetNumberOfK($data, $k) 

{

        $left=getLeft($data,$k);

        $right=getRight($data,$k);

        return $right-$left+1;

}

function getLeft($arr,$k){

        $left=0;

        $right=count($arr)-1;

        $mid=intval($left+($right-$left)/2);

        while($left<=$right){

                if($arr[$mid]>=$k){//关键

                        $right=$mid-1;

                }else{

                        $left=$mid+1;

                }   

                $mid=intval($left+($right-$left)/2);

        }   

        return $left;

}

function getRight($arr,$k){

        $left=0;

        $right=count($arr)-1;

        $mid=intval($left+($right-$left)/2);

        while($left<=$right){

                if($arr[$mid]<=$k){//关键

                        $left=$mid+1;

                }else{

                        $right=$mid-1;

                }   

                $mid=intval($left+($right-$left)/2);

        }   

        return $right;

}

$arr=array(1,2,3,4,4,4,5);

$m=GetNumberOfK($arr,4);

var_dump($m);

  

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
巧用 PHP 数组函数

0x00 前言 PHP 的数组是一种很强大的数据类型,与此同时 PHP 内置了一系列与数组相关的函数可以很轻易的实现日常开发的功能。但是我发现好像很多小伙伴都忽略了内置函数的作用(比如我自己就...

osc_qxef12bc
2018/08/20
2
0
牛客网数组中出现次数超过一半的数字

题目描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如...

osc_gl1bo05e
2019/03/23
3
0
算法:数组处理

算法:数组处理 数组中出现次数超过一半的数字 题目描述   数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如,输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}由于数字2在数...

osc_6ddefhon
2018/03/28
0
0
剑指Offer(Java版):数字在排序数组中出现的次数

题目:统计一个数字在排序数组中出现的次数。例如输入排序数组为 {1,2,3,3,,3,3,4,5}和数字3,由于3在这个数组中出现了4次,因此输出4 既然输入的数组是排序的,那么我们很自然的想到利用二分...

一贱书生
2016/08/03
12
0
数字再排序数组中出现的次数

题目:统计一个数字在排序数组中出现的次数。例如输入排序数组 {1, 2, 3, 3, 3, 3, 4, 5}和数字 3,由于 3 在这个数组中出现了 4 次,因此输出为 4 。 由于输入的是排序数组,很自然的...

passionfly
2014/11/27
14
0

没有更多内容

加载失败,请刷新页面

加载更多

图解ARP协议(二)ARP***原理与实践

一、ARP***概述 在上篇文章里,我给大家普及了ARP协议的基本原理,包括ARP请求应答、数据包结构以及协议分层标准,今天我们继续讨论大家最感兴趣的话题:ARP***原理是什么?通过ARP***可以做...

osc_91g5cdgs
13分钟前
0
0
shell进度条实现

#!/bin/bashb=''i=0while [ $i -le  100 ]do    printf "progress:[%-50s]%d%%\r" $b $i    sleep 0.1    i=`expr 2 + $i`            b=#$b......

osc_npw5uz1o
14分钟前
13
0
通过ssh实现登录服务器脚本

版本v1 #!/bin/bash########################author: Bovin########################show all host infos of serverList.txtif [[ -f $HOME/.serverList.txt ]]then  hos......

osc_lt2jwwhb
16分钟前
0
0
VMware Fusion下Centos联网

1.VMware Fusion设置选择“网络适配器” 2.“连接我的网络适配器”选择“与我的mac共享” 3.编辑centos的ip配置文件 [root@Centos ~]# more /etc/sysconfig/network-scripts/ifcfg-eth0D...

osc_pg5rp78i
17分钟前
0
0
Kickstart配置文件参数详解

kickstart是什么? KickStart是一种无人值守的安装方法。它的工作原理时在安装过程中记录典型的需要人工干预填写的各种参数,并生成一个名为ks.cfg的文件。如果在安装过程中(不只局限于生成K...

osc_r9yyhhqz
18分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部