本文共 1458 字，大约阅读时间需要 4 分钟。

题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

思路

两种思路都试一下，现在就能更明确力扣的判时就假的一批。

二分法竟然比顺序找还慢

重点说下二分法的思路

算法解析：

• 初始化： 左边界 i = 0，右边界 j = len(nums) - 1；代表闭区间 [i, j]。
• 循环二分： 当 i≤j 时循环 （即当闭区间 [i, j] 为空时跳出）；
• 计算中点 m = (i + j) // 2，其中 "//" 为向下取整除法；
  • 若 nums[m] = m ，则 “右子数组的首位元素” 一定在闭区间 [m + 1, j]中，因此执行 i = m + 1；
  • 若 nums[m] ≠ m ，则 “左子数组的末位元素” 一定在闭区间 [i, m - 1] 中，因此执行 j = m - 1；
• 返回值： 跳出时，变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可。

链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/

代码（顺序查找）

class Solution {public:    int missingNumber(vector
   
    & nums) {                if(nums.size() == 1){            if(nums[0] == 0)                return 1;            else                return 0;        }                        for(int i = 0;i < nums.size();i++){            if(nums[i] != i){                return i;            }        }        return nums.size();    }};
   

代码（二分法）

class Solution {public:    int missingNumber(vector
   
    & nums) {                if(nums.size() == 1){            if(nums[0] == 0)                return 1;            else                return 0;        }                int i = 0;        int j = nums.size() - 1;        int m = 0;        while(i <= j){            m = (i + j) / 2;            if(nums[m] == m){                i = m+1;            }else{                j = m-1;            }        }        return i;    }};
   

转载地址：https://blog.csdn.net/hanmin822/article/details/106011391 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！