Leetcode基础刷题之PHP解析(268. Missing Number)
2019-4-18 星期四 开始吧
上一题链接 Leetcode基础刷题之PHP解析(263. Ugly Number)
题目描述
查找缺失的数。给你一组数组,查找从0-n中缺少的整数。有点坑爹的是如果给你的是[0,1,2],为了返回回来的都是有缺失的数,所以这里应该返回3。
题目分析
解法很多。第一种就是迭代他哪个位置空缺返回哪个数,如果都没有返回数组最后一个数加1。
/** * @param Integer[] $nums * @return Integer */ function missingNumber($nums) { sort($nums); for($i=0;$i<count($nums);$i++){ if(!in_array($i,$nums)){ return $i; } } return $nums[count($nums)-1]+1; }
解法二
使用二分查找,每次获取中间元素的下标和下标对应的值进行比较,如果下标对应的值大于元素下标,说明缺失的数字在右边,把右边赋值给中间下标,否则左边就来到中间下标的下一个位置。
/**
* @param Integer[] $nums
* @return Integer
*/
function missingNumber($nums) {
sort($nums);
$left=0;$right=count($nums);
while($left<$right){
$mid=$left+intval(floor(($right-$left)/2));
if($nums[$mid]>$mid) {
$right=$mid;
}else{
$left=$mid+1;
}
}
return $right;
}
解法三
可能你已经发现了, 以上两个操作都先把数组进行排序,那么在效率上就....,所以还能不能有其他解法,异或。因为0-n之间缺少一个数,我们只要把完整的数组和缺少1个的数组异或一下,相同的都变成0,多出来的当然就是缺少的哪个数。
/**
* @param Integer[] $nums
* @return Integer
*/
function missingNumber($nums) {
$res=0;
for($i=0;$i<count($nums);$i++){
$res ^=($i+1) ^ $nums[$i];
}
return $res;
}
Github整理地址:https://github.com/wuqinqiang/leetcode-php
No Comments