268.md

✏️Leetcode之PHP版题目解析（268. Missing Number）

2019-04-18 吴亲库里 库里的深夜食堂

---

✏️描述

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

---

联系

​