登录
注册
首页
开源社群
PHP
PHP如何实现查找缺失数字
PHP如何实现查找缺失数字
开源社区
2022-12-14 14:30:58
0
1363
PHP 计算0~n-1中缺失的数字 0~n-1中缺失的数字 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。 示例 1: ```bash 输入: [0,1,3] 输出: 2 ``` 示例 2: ```bash 输入: [0,1,2,3,4,5,6,7,9] 输出: 8 ``` 解题思路 简单的二分查找,题意明确了所有数是递增的,且所有数的取值范围均在 [0, n-1] 上并且是唯一的,因此可以发现这样一个规律: 只要查询过程中 nums[i] == i,那么缺失的值一定在i的右侧; 如果查询过程中 nums[i] > i,那么缺失的值一定在左侧; 所以最后只要返回 min 即为结果。 代码 ```php function missingNumber($nums) { $min = 0; $max = count($nums) - 1; while ($min <= $max) { $mid = (int)($min + ($max - $min) / 2); $mid == $nums[$mid] ? $min = $mid + 1 : $max = $mid - 1; } return $min; } ```
评论
此内容暂不接受评论!
最新帖子
echarts是什么
echarts中文官网
php通过生日计算年龄
PHP代码标记
form表单处理
实用的脚本
什么是 PostgreSQL?
什么是 MySQL?
filezilla是什么
什么是html
热门帖子
标注
×
请输入标注内容(最多8个字符):
返回顶部
thinksaas
在线咨询
关注公众号