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

这个题正确的选择应该使用二分法

题目描述:

难度简单42

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

一.最简单的方法

就是数组中的元素和对应的下标不相同就返回这个下标

遍历结束就返回这个数组的长度;

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

最坏情况要遍历整个数组 所以时间复杂度是O(n);

二.二分法

思路: 根据题意,我们可以用二分法来解答;先将 left = 0; right = nums.size() ;left = right 循环结束;middle 取 left 和 right 中间的元素如果 nums[middle] == middle ; 说明 middle 和left的区间内左边不可能出现这个不在数组中的数字;往右边找这个不在数组中的数字; 将left 和 right 这个区间缩小;left = middle +1 ;排除一半的数据;如果nums[middle] != middle 说明这个不在数组中的数字可能出现在left 和 middle 区间内; 将left 和 right 这个区间缩小; right = middle;循环结束时left 或者right就是那个不在数组中的数字;因为此时left == right;

class Solution {public:    int missingNumber(vector
   
    & nums) {		int left = 0,right = nums.size();		        while (left < right) {            //使用(left + right)/2 也可以 但是要注意 left + right 可能会超过 int 表示范围            //left + (right - left )/2 可以有效的 防止溢出;            int middle = left + (right - left)/2;            if (middle == nums[middle]) {			 	left = middle + 1;            } else {                right = middle;            }                    }        		return left;    }};
   

时间复杂度为O(log(n));

注:

有一种是利用求和公式,我的数学是体育老师教的 求和公式: n*(n +1)/2;但是我不知道为啥,所以我不敢去写;

转载地址：http://abyki.baihongyu.com/