【二分查找专题】剑指 Offer 53 – II. 0～n-1中缺失的数字-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年4月8日下午8:57

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0;
        int j = nums.length;
        while(i < j){
            int mid = (j-i)/2 + i;
            if(mid == nums[mid]){
             // 0-mid都满足
                i = mid + 1;
            }else{
                j = mid;
            }
        }
        return i;

    }
}

0 赞同 0 条回复

cute. 普通 2023年4月3日下午4:50

var missingNumber = function(nums) {
    var left = 0;right = nums.length-1;
    while(left<=right){
        var mid = Math.floor((left+right)/2);
        if(nums[mid]==mid)left = mid+1;//说明此时左半边无误，缺失在右半边
        if(nums[mid]>mid)right = mid-1;//说明此时左半边已缺失，另外不会有n[m]<m的情况，那不会是缺失只会是多出
    }
    return left;
};

时间复杂度: O(logN)
空间复杂度: O(1)

0 赞同 0 条回复

宁永久会员 2023年1月14日上午11:44

自己做的时候没有想到return还要区分

class Solution {
    public int missingNumber(int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        while(l < r){
            int mid = (r - l) / 2 + l;
            if(nums[mid] == mid){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return nums[r] == r ? r + 1 : r;//如果数组完整证明缺少最后一个元素
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月9日下午1:01

'''
思路：
根据题意可以发现：如果开头和中间不存在遗漏的数字，则数组和数组的索引是一样的，所以如果nums[mid] == mid说明mid之前的内容是没有遗漏数字的，如果nums[mid] > mid,说明在[l,mid]之间存在遗漏
这里不可能出现nums[mid] < mid的情况（因为数组的递增的，如果出现遗漏，也只会是索引小于对应元素）
注意：
如果遗漏数字是首尾的情况
'''


def missingNumber(nums):
    l = 0
    r = len(nums) - 1
    # 如果第一数不是0 ，说明0被遗漏了
    if nums[l] != 0:
        return 0
    # 如果中间不存在遗漏的数字，说明最后一个数加一就是
    if nums[r] == r:
        return r+1
    while(l < r):
        # 向下圆整
        mid = l + (r - l) // 2
        if nums[mid] == mid:
            l = mid + 1

        # 不可能出现nums[mid] < mid的情况
        elif nums[mid] > mid:
            r = mid
    return l

0 赞同 0 条回复

lucca 普通 2023年1月7日下午4:09

class Solution {
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] == mid) l = mid + 1;
            else r = mid;
        }
        return nums[l] != l ? l : nums.length;
    }
}

时间复杂度: O(logN)
空间复杂度: O(1)

0 赞同 0 条回复

感到自己好渺小普通 2022年12月6日下午8:31

class Solution {
    // 排序数组中的搜索问题，首先想到 二分法 解决。
    // 排序数组中使用双指针也是高频选项
    /* 
        根据题意，数组可以按照以下规则划分成两部分
        左子数组：nums[i] == i
        右子数组：nums[i] != i
        缺失的数字等于“右子数组的首位元素”，也就是在 判断条件 为nums[i] != i，求其左边界
    */
    public int missingNumber(int[] nums) {
        int l = 0;
        int r = nums.length;
            while(l < r)
            {
                int mid = l + r>> 1;
                if(nums[mid] != mid) r = mid;
                else l = mid + 1; 
            }
            return l;
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:25

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //使用二分查找，左闭右开
        int l= 0;
        int r = nums.size();
        while(l<r){
            int m = l+(r-l)/2;
            if(nums[m]>m) r = m;
            else if(nums[m]==m) l = m+1;
        }
        return l;

    }
};

0 赞同 0 条回复

xye 普通 2022年11月23日下午2:16

func missingNumber(nums []int) int {
    if len(nums) == 0 {
        return -1
    }
    l := 0
    r := len(nums) - 1
    var mid int
    for l <= r {
        mid = l + (r - l) / 2
        if nums[mid] != mid {
            r = mid - 1
        }else{
            l = mid + 1
        }

    }
    return l
}

时间O（logN）空间O（1）

0 赞同 0 条回复

刺猬普通 2022年11月19日下午6:20

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        int mid;
        while(l < r) {
            mid = (l + r) / 2;
            if(nums.at(mid) == mid)
                l = mid + 1;
            else 
                r = mid;
        }
        if(nums.at(l) == l)
            return l + 1;
        else
            return l;
    }
};

时间复杂度：log(n)
额外空间复杂度：O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月19日下午4:07

时间复杂度：O(logn)
零件复杂度：O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # nums[mid] 和mid 做对比，只可能存在相等或者nums[mid] > mid的情况，相等查找范围在[mid+1,R],另外一种情况查找范围在[L,mid-1]
        L, R = 0, len(nums) - 1
        while L <= R:
            mid = L + (R - L) // 2
            if nums[mid] == mid:
                # [mid + 1, R]
                L = mid + 1
            else:
                # [L, mid - 1]
                R = mid - 1
        return L

0 赞同 0 条回复

黎昕普通 2022年11月12日下午11:04

直接遍历：
时间 O(n) 空间 O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums[i]!=i:
                return i
        return len(nums)

二分查找
时间 O(logn) 空间 O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == m: i = m + 1
            else: j = m - 1
        return i

0 赞同 0 条回复

小肸永久会员 2022年11月12日下午7:50

思路一：定义一个变量i=0,拿i和nums[i]做比较，相等i++，否则返回i。时间复杂度O(N)，空间复杂度O(1)。

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

思路二：对0到n-1之间的数求和，然后对nums数组中所有的数求和，得到的差值就是缺失的那个数字，时间复杂度O(N)，空间复杂度O(1)。
思路三:通过二分的思想不断的缩小范围。时间复杂度O(N),空间复杂度O(1)。

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1;
        // while中判断条件是left <= right 可以省去判断[0,1,2]这类情况
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                // [0, 1, 3]写成right = mid, 会出现死循环，主要是while的判断条件是left<=right
                right = mid - 1;
            }
        }
        return left;
    }
}

0 赞同 0 条回复

Y7n05h 普通 2022年11月12日下午12:18

class Solution {
public:
    int missingNumber(vector<int> nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            const auto mid = left + (right - left) / 2;
            const auto tmp = nums[mid];
            if (tmp > mid) {
                right = mid - 1;
            } else if (tmp == mid) {
                left = mid + 1;
            } else if (tmp < mid) {
                left = mid + 1;
            }
        }
        return left;
    }
}

时间复杂度：O(lgN)

0 赞同 0 条回复

@ 普通 2022年11月12日上午11:34

思路:二分查找
时间复杂度 O(logN）
**空间复杂度 O(1) **

//如果这个递增数组符合要求，那么该数组的索引一定和当前索引所对应的值是相等的。
class Solution {
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            //如果mid == nums[mid],则左边的元素肯定都符合要求（因为是有序数组），而那个唯一一个不符合的数一定在mid的右边
            if(mid == nums[mid])
                l = mid + 1;
            else{
                //出现这种情况只有可能是mid < nums[mid],说明那个唯一一个不符合的数一定在mid的左边,接下来就一直往左找，直到
                //跳出这个循环,那么l就是那个不符合的数.
                r = mid - 1;

            }

        }

        return l;

    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午6:57

 public int missingNumber(int[] nums) {
        //思路 查找数组index的值和nums[index]是否相等
        //时间复杂度O(lgn)
        //空间复杂度O(1)
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == mid) {
                //前面数组不缺失
                left = mid + 1;
            } else {
                //缺失 左移
                right = mid;

            }
        }
        return left == nums.length - 1 && nums[left] == left ? left + 1 : left;
    }

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午6:57

 public int missingNumber(int[] nums) {
        //思路 查找数组index的值和nums[index]是否相等
        //时间复杂度O(lgn)
        //空间复杂度O(1)
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == mid) {
                //前面数组不缺失
                left = mid + 1;
            } else {
                //缺失 左移
                right = mid;

            }
        }
        return left == nums.length - 1 && nums[left] == left ? left + 1 : left;
    }

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午6:57

 public int missingNumber(int[] nums) {
        //思路 查找数组index的值和nums[index]是否相等
        //时间复杂度O(lgn)
        //空间复杂度O(1)
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == mid) {
                //前面数组不缺失
                left = mid + 1;
            } else {
                //缺失 左移
                right = mid;

            }
        }
        return left == nums.length - 1 && nums[left] == left ? left + 1 : left;
    }

0 赞同 0 条回复

lobort 普通 2022年11月9日下午7:58

class Solution {
    public int missingNumber(int[] nums) {
        //二分法 时间复杂度O(logn)  空间复杂度O(1)
         int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] == mid){
                left = mid + 1;
            }else if(nums[mid] > mid){
                right = mid - 1;
            } 
        }
        return left;
    }

        //直接遍历 时间复杂度O(n) 空间复杂度0(1)
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i){
                return i;
            }
        }
        return nums.length;
    }
}

0 赞同 0 条回复

Whatever 永久会员 2022年11月9日下午7:51

规律：nums[mid] > mid 说明元素在左边，缩小右边边界；反之，元素在右边，缩小左边边界

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > mid){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

0 赞同 0 条回复

just 普通 2022年11月9日上午11:18

//有升序数组二分查找
class Solution {
public:
int missingNumber(vector& nums) {
int l=0,r=nums.size()-1;
int res=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]mid) l=mid+1;
else r=mid-1;
}
res=l;
return res;
}
};

0 赞同 0 条回复

天然普通 2022年11月9日上午9:24

想到了加法求和，先把左右边界控制了，则数组内左+右=nums[0]+nums[-1],二分遍历，大于总值，说明左边缺数，反之亦然
时间复杂度O(logn)
空间复杂度O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if not nums or nums[0]!=0: return 0
        if nums[-1]!=len(nums):return len(nums)
        if len(nums)==2 and nums[-1]==len(nums):return 1
        left ,right= 0,len(nums)-1
        scan = nums[0]+nums[-1]
        while (left<=right):
            if nums[left]+nums[right]>scan:
                return nums[left]-1
            elif nums[left]+nums[right]<scan:
                return nums[right]+1
            else:
                right = right-1
                left = left+1

0 赞同 0 条回复

y 普通 2022年11月8日下午10:05

//  寻找 nums[mid] 大于等于 mid 的右边界
var missingNumber = function(nums) {
  let l = 0;
  let r = nums.length - 1;
  while(l <= r) {
      let mid = Math.floor((r + l) / 2);
      if(nums[mid] === mid) {
          l = mid + 1;
      } else {
          r = mid - 1;
      }
  }
  return l;
};

0 赞同 0 条回复

易水寒永久会员 2022年11月8日下午3:27

左闭右闭

class Solution {
    public int missingNumber(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while(l <= r) {
            int mid = l + (r-l)/2;
            if(mid == nums[mid]) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return l;
    }
}

0 赞同 0 条回复

派大星普通 2022年11月7日下午10:11

class Solution {
//使用二分查找法，若中间节点的值发生异常则将右标记往前移，无异常则左标记往后移   
public int missingNumber(int[] nums) {
        if(nums == null||nums.length==0)return 0;
        int l = 0,r = nums.length - 1;
        int m = 0;
        while(l != r){
            m = (l+r)/2;
            if(nums[m] == m){
                l = m + 1;
            }else
                r = m;
        }
        return l==nums[l] ? nums.length : l;
   }
}

0 赞同 0 条回复

庄重普通 2022年11月7日下午8:39

// 思路：
//     1.排序序列使用二分查找
//     2.通过判断下标和下标对应value是否相等,来看需要找的数字在哪边
//     3.true:符合要求，l指针右移至mid
//     4.false：不符合要求，r指针左移至mid
//     5.从而缩小范围，找到第一个不符合要求的值
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0 ,r = nums.size()-1;

        int mid = 0;
        while(l < r){
            mid = l + (r - l) / 2;
            if(nums[mid] == mid)
                l = mid +1;
            else
                r = mid;
        }
        //缺少的元素为最后一个值的时候，也就是缺少n的时候，需要对l+!
        return nums[l] == l ? l + 1 : l;
    }
};
//时间复杂度O(logn)
//空间复杂度O(1)

0 赞同 0 条回复

你有点可爱喔普通 2022年11月7日下午7:39

空间复杂度O(1)
时间复杂度O(logn)

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0,right = nums.length-1;
        while(left<=right){
            int mid = (right-left)/2+left;
            if(nums[mid] == mid){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return left;

    }
    //     int num = 1;
    //      for(int i = 0;i<nums.length;i++){
    //         if(i!=nums[i])return i;
    //      return nums.length;
    // }}

}

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月7日下午7:33

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

空间复杂度O(1)
时间复杂度O(logn)
本来想用别的方法做的，还是用了二分查找，自己画的图

0 赞同 0 条回复

T 普通 2022年11月7日下午4:49

下面是代码

class Solution {
    public int missingNumber(int[] nums) {
        int low = 0, high = nums.length - 1;
        while(low <= high) {
            int mid = low + ((high - low) >> 1);
            if(nums[mid] == mid) 
                low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }
}

0 赞同 0 条回复

青木普通 2022年11月7日下午3:54

/**
    时间复杂度O(logn)
    空间复杂度O(1)
 */
class Solution {
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1, ans = nums.length;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] == mid){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return l;
    }
}

0 赞同 0 条回复

优秀市民普通 2022年11月7日下午3:25

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0,j = nums.length - 1;
        while(i <= j){
            int mid = (i + j) / 2;
            if(nums[mid] == mid){
                i = mid + 1;
            }else{
                j = mid - 1;
            }
        }
        return i;

    }
}

找到与nums[mid]不想等的索引就可以判断，一定存在这个数

0 赞同 0 条回复

So 普通 2022年11月7日下午12:23

class Solution {
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == mid) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l] == l ? l + 1 : l;
    }
}

时间：O(log(n))，空间：O(1)

0 赞同 0 条回复

一只骆驼普通 2022年11月7日上午11:47

时间复杂度为O（logn），空间复杂度为O（1）

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right =nums.length-1;
        while(left<=right){
            int mid = (right-left)/2+left;
            if(nums[mid]==mid){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
}

0 赞同 0 条回复

追普通 2022年11月7日上午10:59

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] == mid) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
};

使用二分查找，注意最终的返回值

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月7日上午1:20

时间复杂度为O（lgn），空间复杂度为O（1）

class Solution {
    public int missingNumber(int[] nums) {

        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] == mid){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[right] == right ? right+1:right;
    }
}

0 赞同 0 条回复

cxc 普通 2022年11月6日下午11:16

class Solution {
    public int missingNumber(int[] nums) {
        if (nums[0]==1) return 0;
        for (int i = 0;i<nums.length;i++){
        //只要比较数组下标和该下标对应的值即可，再排除缺失0和缺失最后一项两个特殊情况。
            if (nums[i]!=i) return i;
        }
        return nums.length;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月6日下午9:18

log(n)

/**
左数组：满足下标等于值
右数组：下标不等于值
 */
class Solution {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == mid){
                //满足左数组,则右数组的起始位置一定在[mid+1,right]
                left = mid + 1;
            }else if(nums[mid] != mid){
                //满足右数组，则左数组的末尾一定在[left,mid-1]
                right = mid - 1;
            }
        }
        return left;//返回右数组的起始位置
    }
}

0 赞同 0 条回复

Error 普通 2022年11月6日下午6:06

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == m:
                i = m + 1
            else:
                j = m - 1
        return i

二分查找
时间复杂度 O logn

0 赞同 0 条回复

是梦终空永久会员 2022年11月6日下午5:45

时间O(n)
空间O(n)

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n-1;
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid] == mid){
                l = mid+1;
            }else{ 
                r = mid;
            }
        }
        if(nums[l] == l)    return l+1;
        return l;
    }
}

0 赞同 0 条回复

【二分查找专题】剑指 Offer 53 – II. 0～n-1中缺失的数字

共以下 38 个回答

# 回答此问题取消回复

【二分查找专题】剑指 Offer 53 – II. 0～n-1中缺失的数字

共以下 38 个回答

# 回答此问题 取消回复

# 回答此问题取消回复