九号球普通 2023年11月20日上午8:37

“`java
缺失的可能是最后一个，也可能是中间的
class Solution {
public int takeAttendance(int[] records) {
int l = 0;
int r = records.length – 1;
while (l < r) { int mid = l + (r - l)/2; if (records[mid] == mid) { l = mid + 1; } else { r = mid; } } return records[l] == l ? l + 1 : l; } }

0 赞同 0 条回复

招舟子普通 2023年8月31日上午10:49

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

}
注意向下取整和向上取整

0 赞同 0 条回复

jhfuture 普通 2023年8月18日下午11:26

“`java
时间复杂度为O(logn) 空间为O(n)
class Solution {
public int missingNumber(int[] nums) {
if(nums.length==0) return -1;

    int l=-1;
    int r=nums.length;
    while(l+1!=r){
        int middle=(l+r)/2;
        if(nums[middle]==middle){
            l=middle;
        }else{
            r=middle;
        }
    }
    if(l==-1){
        return nums[r]-1;
    }else if(r==nums.length){
        return nums[l]+1;
    }



   return nums[l]+1;
}

}

0 赞同 0 条回复

CV大神普通 2023年8月15日下午8:50

public int missingNumber(int[] nums) {
         if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
           //不相等，说明左边有缺失
            if (nums[middle] != middle) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return left;
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:47

“`C++
int findMissingNumber(vector& nums) {
int left = 0;
int right = nums.size() – 1;

// 使用二分查找找到缺失的数字
while (left <= right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] == mid) {
        left = mid + 1;
    } else {
        if (mid == 0 || nums[mid - 1] == mid - 1) {
            // 如果 mid 是第一个不满足 nums[mid] == mid 的位置，则 mid 对应的数字就是缺失的数字
            return mid;
        }
        right = mid - 1;
    }
}

// 如果所有数字都满足 nums[mid] == mid，则缺失的数字是 n
return nums.size();

}

“`

0 赞同 0 条回复

彦，，# 普通 2023年7月15日下午11:42

利用二分法
int missingNumber(vector<int>& nums) {
        int l = 0;
        int r = nums.size() -1;
        while(l <=  r)
        {
            int mid = (r + l)/2;
            if(nums[mid] == mid)
            {
                l = mid + 1; 
            }else {
                r = mid -1 ; 
            }
        }
        return l;
    }

0 赞同 0 条回复

Sexypig. 普通 2023年7月14日下午8:04

较难解释。
运用leftBound模板，最后会位于缺失数字左边，返回left即缺失数字。

#include <iostream>
using namespace std;
#include <vector>

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

int main() {
    vector<int> arr = {0, 1, 2, 3, 5, 6, 7, 8, 9};
    cout << Solution().missingNumber(arr) << endl;
    return 0;
}

0 赞同 0 条回复

BOZ 普通 2023年7月12日下午4:16

【思路】找到第一个value大于index的元素，可以利用二分查找加速
【复杂度】时间O(logn)，空格O(1)

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

0 赞同 0 条回复

江畅普通 2023年7月12日下午3:30

// 0～n-1中缺失的数字
// 时间复杂度 O(logN)
// 空间复杂度 O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == mid) { left = mid + 1; }
            else { right = mid - 1; }
        }
        return left;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月12日下午1:04

直接找目标值就可以了

class Solution {
    public int missingNumber(int[] nums) {
        if(nums==null||nums.length<=0){
            return -1;
        }

        int left=0;
        int right=nums.length-1;

        while(left<right){
            int mid=(right-left)/2+left;
            if(nums[mid]>mid){
                right=mid;
            }else{
                left=mid+1;
            }
        }

        return left==nums[left]?left+1:left;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月11日上午11:59

java
class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length <= 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = (right - left)/2 + left;
            if(nums[mid] == mid) { //mid前面的顺序都没问题
                left = mid + 1;
            } else { //nums[mid] != mid //mid前面的顺序有问题
                right = mid - 1;
            }
        }
        if(nums[left] == left) {  //[0,1,2]等这种情况，最后需要+1，right一直左移最后等于left的情况
            return nums[left] + 1;
        }
        //[1,2,3]这种情况，最后需要-1，left一直右移最后等于right退出的情况
        return nums[left] - 1;
    }
}

时间复杂度O(LOGN)

0 赞同 0 条回复

屠龙手段普通 2023年7月9日下午9:28

二分查找递归写法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if nums[0] != 0:
            return 0
        return self.binarySearch(nums, 0, len(nums) - 1)
    
    def binarySearch(self, nums, left, right):
        mid = (right - left) // 2 + left
        if left > right:
            return left  
        return self.binarySearch(nums, mid + 1, right) if nums[mid] == mid else self.binarySearch(nums, left, mid - 1)

0 赞同 0 条回复

残月冷骄阳普通 2023年7月9日下午8:12

复杂度

时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$

Code

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

        return left;
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月6日上午10:04

二分去找不在正确位置上的数字

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

0 赞同 0 条回复

局外人普通 2023年7月6日上午9:21

思路：按照规律观察 nums[mid] 和 mid 的关系，如果 nums[mid] 和 mid 相等，则缺失的元素在右半边，如果 nums[mid] 和 mid 不相等，则缺失的元素在左半边。
时间复杂度O(logn) 空间复杂度O(1)

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

0 赞同 0 条回复

Ming 普通 2023年7月5日上午10:09

时间复杂度：log(n)
额外空间复杂度：O(1)
向右边寻找消失的数字

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;
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月4日下午11:48

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        l, r = 0, len(nums)

        while l < r:
            m = (r - l) // 2 + l
            if (nums[m] == m):
                l = m + 1
            else:
                r = m

        return l

通过idx判断

0 赞同 0 条回复

Jerry 普通 2023年7月4日下午10:35

class Solution {
    public int missingNumber(int[] nums) {
        if (nums[0] == 1) return 0; //排除0的情况
        for (int i = 0; i < nums.length; i++) {
            int index = i;
            int value = nums[i];
            if (index != value) return index;
        }
        return nums.length; //排除缺失最后一项的情况
    }
}

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午9:23

二分查找

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

0 赞同 0 条回复

yxy 普通 2023年7月4日下午8:26

时间复杂度O(logn)

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

0 赞同 0 条回复

张开怀普通 2023年7月4日上午9:28

class Solution{
public:
       int missingNumber(vector<int>& nums){
              int l = 0, r = nums.size() - 1;
              while(l < r){
                     int mid = l + (r -  l)/2;   // 向下取整
                     if(nums[mid] == mid){
                            l = mid +1;
                     }else{
                            r = mid;
                     }
              }
              return num[l] == l ? l+1: l;   // 一整个数组都是完整的数组，缺失的那个数字是最后一个数，即n
       }
}

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

0 赞同 0 条回复

行动派小彩笔普通 2023年7月4日上午12:49

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月3日下午11:13

//时间O(logn) 空间O(1)
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 条回复

伏月三十普通 2023年7月3日下午10:31

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;
    }
}

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

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月3日下午9:59

时间复杂度：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) >> 1);
            if(nums[mid] != mid){
                r = mid; 
            } else {
                l = mid + 1;
            }
        }
        return nums[l] == l ? l + 1 : l;

    }
}

0 赞同 0 条回复

小吕普通 2023年7月3日下午9:33

c++实现
int missingNumber(vector& 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 条回复

花老爷普通 2023年7月3日下午6:09

二分查找
时间：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) / 2;
            if (nums[mid] == mid) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l == nums[l] ? l + 1 : l;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年7月3日下午4:13

MY

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=-1,r=nums.size();
        while(l+1 != r){
            // 左区域 ns[i] == i,右区域 ns[i] != i
            int mid = l+(r-l)/2;
            if(nums[mid] == mid) l=mid;
            else r=mid;
        }
        return r;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月3日下午2:17

//方法一：二分查找  时间复杂度O(nlogn) 空间复杂度O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<=r)
        {
            int mid=(r+l)/2;
            if(nums[mid]>mid) r=mid-1;
            else l=mid+1;
        }
        return l;
    }
};
//方法二：顺序遍历  时间复杂度O(n) 空间复杂度O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int length=nums.size();
        int i;
        for(i=0;i<length;i++)
        {
            if(nums[i]!=i)
            {
                return i;
            }
        }
        return i;
    }
};

0 赞同 0 条回复

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

共以下 29 个回答

复杂度

Code

MY

# 回答此问题取消回复

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

共以下 29 个回答

复杂度

Code

MY

# 回答此问题 取消回复

# 回答此问题取消回复