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

桎梏普通 2023年9月16日下午3:15

class Solution {
    public int missingNumber(int[] nums) {
        //寻找第一个值不等于其索引的 "索引"
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == mid){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }
}

0 赞同 0 条回复

ppopp 普通 2023年8月30日下午10:52

class Solution {
public:
int missingNumber(vector& nums) {
int len = nums.size();
int left = 0;
int right = len;

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

};//滴滴

0 赞同 0 条回复

hi 普通 2023年8月16日上午9:40

该题具有二段性（等于或者不等于），利用二分法来解决
当查找的数组元素与下标都一一对应时，那么缺失的数就是最后一个数，而此时r还在最后面，那么缺失的就是r++

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

        if(nums[r] == r) r++;

        return r;
    }
};

0 赞同 0 条回复

doordie. 普通 2023年8月14日下午3:19

class Solution {
       public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length -1;
        while (left <= right){
            int mid = (right - left) / 2 +left;
            // 如果相等 说明“右子数组的首位元素”一定在[mid+1,right]
            if (nums[mid] == mid){
                left = mid + 1;
            // 如果不相等 说明“左子数组的末位元素”一定在[left,mid-1]
            }else {
                right = mid - 1;
            }
        }
        return left;
    }
}

时间复杂度：O（logN）

0 赞同 0 条回复

艺普通 2023年8月3日下午9:38

“`c++
//时间复杂度： O（logn)
//空间复杂度： O (n)
class Solution {
public:
int missingNumber(vector& nums) {
int n=nums.size();
int l=0,r=n-1;
while(l<=r) { int m=l+(r-l)/2; if(nums[m]==m) l=m+1; else { while(m>=0&&nums[m]!=m) m–;
return m+1;
}
}
return n;
}
};

0 赞同 0 条回复

普通 2023年7月31日下午10:24

c++ 二分查找
lass Solution {
public:
int missingNumber(vector& nums)
{
int r=nums.size()-1,i;
int l=0;
while(l<r)
{
int mid=(r-l)/2+l;
if(nums[mid]!=mid)
r=mid;
else
l=mid+1;

    }
    return l==nums.size()-1&&nums[l]==l?l+1:l;
}

};

0 赞同 0 条回复

波雅汉库克普通 2023年7月31日下午3:29

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums.size()==1){
            return nums[0]==1?0:1;
        }
        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{
                right = mid - 1;
            }
        }
        if(nums[left]==left){
            return left+1;
        }
        return left;
    }
};

时间复杂度： O（logn)
空间复杂度： o (n)

0 赞同 0 条回复

CaCO3 永久会员 2023年7月31日上午11:10

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

0 赞同 0 条回复

枫梓。普通 2023年7月27日下午3:38

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

二分找缺失。时间O(logn)

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月26日下午11:04

class Solution {
    public int missingNumber(int[] nums) {
        // 简单方法：即遍历数组，找到下标和值不相等的那个值
        // 进阶：二分查找，数组分为两部分，前半部分下标和值相等，后半部分下标和值不相等
        // 找到后半部分的第一个坐标
        int left = 0;
        int right = nums.length-1;
        int mid;
        while(left<=right){
            mid = (right-left)/2+left;
            if(mid==nums[mid]){
                left = mid + 1;
            } else{
                right = mid-1;
            }
        }
        return left;
    }
}

时间复杂度：O（logn）
空间复杂度：O（1）

0 赞同 0 条回复

北辰普通 2023年7月26日下午9:00

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int n = len+1;
        int ans=0;
        boolean[] isPresent = new boolean[n];
        Arrays.fill(isPresent, false);
        for(int i=0;i<len;i++) {
            isPresent[nums[i]]=true;
        }
        for(int i=0;i<n;i++) {
            if(isPresent[i]==false) {
                ans=i;
            }
        }
        return ans;
    }
}

比较拉跨的方法

0 赞同 0 条回复

CKX 普通 2023年7月26日下午3:05

func missingNumber(nums []int) int {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] > mid {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

时间O(logn)
空间O(1)

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月25日下午9:10

代码

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;
            }
        }
        return nums[left]==left?left+1:left;
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年7月25日上午11:49

class Solution {
public int missingNumber(int[] nums) {
//二分找到左边开始第一个不与下标相等的第一个元素
//左边等于下边右边不等于左边开始走反正左边一直往右走
int left =0;
int right = nums.length-1;
int mid;

    while(left<=right)
    {
        mid =(left+right)/2;
        if(nums[mid]>mid)  //一定在左边 
        {
            right =mid - 1;
        }
        if(nums[mid]==mid) // 一定在右边
        {
            left =mid + 1;
        }

    }
    return left;
}

0 赞同 0 条回复

Marshan 普通 2023年7月24日下午8:58

没想到利用下标和value相等

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(mid == nums[mid]){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return nums[l] == l ? l+1 : l;
    }

};

0 赞同 0 条回复

mpweixin用户普通 2023年7月24日下午8:34

// 最拉跨的方法
class Solution {
    public int missingNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= nums.length; i++) {
            map.put(i, i);
        }
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.remove(nums[i]);
            }
        }
        for (Integer value : map.values()) {
            return value;
        }
        return -1;
    }
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月23日下午11:12

比较恶心的是一个测试案例的，所以搜索范围要扩大一点

function missingNumber(nums: number[]): number {
    let l = 0, r = nums.length;
    while(l < r) {
        let mid = (l + r) >>> 1;
        if(nums[mid] != mid) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
};

0 赞同 0 条回复

Mby 普通 2023年7月23日下午9:19

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月23日下午3:18

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

        while(l <= r){
            int mid = l + ((r - l) >> 1);

            if(mid  != nums[mid]){//代表左边是无序的，所以缺少的数在左边，去左边找
                r = mid - 1;
            }else{//右边无序
                l = mid + 1;
            }
        }
        if(r < 0) return 0;
        if(l >= nums.length) return nums[nums.length - 1] + 1;
        return nums[r] + 1;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月23日下午2:46

class Solution {
    public int missingNumber(int[] nums) {
        int l=0,r=nums.length-1;
        while(l<=r){
            //l寻找第一个不符合条件的数的位置
            //r寻找符合条件的最后一个数的位置
            int mid=(r-l)/2+l;
            if(nums[mid]==mid){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
}

0 赞同 0 条回复

#00456B 普通 2023年7月23日上午12:10

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            //不存在mid > nums[mid]的情况
            if(nums[mid] > mid){
                //mid和nums[mid]不对应，说明左边被删了元素，右边界缩小
                right = mid - 1;
            }
            else{
                //mid == nums[mid]，说明在右边删除了元素
                left = mid + 1;
            }
        }
        return left;
    }
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月22日下午11:40

7.22
Day14：下面是代码

 

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

    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月22日下午6:22

正常情况下，也就是不缺失的情况下，nums[i] 和其下标i 是一一对应的，因为缺失，而造成有一个地方是不对应的，我们需要找到这个地方。
此时就可以把二分思想中的target想成下标值，想清楚这个，就和一般的二分题毫无区别了。

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) r = mid - 1;
            else if(nums[mid] <= mid) l = mid + 1;
        }
        return l;
    }
}

0 赞同 0 条回复

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

共以下 23 个回答

# 回答此问题取消回复

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

共以下 23 个回答

# 回答此问题 取消回复

# 回答此问题取消回复