Leetcode基础刷题之PHP解析(268. Missing Number)

2019-4-18 期四  

 Leetcode基础刷题之PHP解析(263. Ugly Number)

13b8f6a29c7f9df0a812e65fa5b9e697.png

查找缺失的数。给你一组数组,查找从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


吴亲库里 has written 98 articles

情绪只是对自己无能的愤怒

积分:4772 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?