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

栏目: PHP · 发布时间: 7年前

2 0 1 9 - 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;
    }