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

YOLO 普通 2024年4月12日下午9:39

/*一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 */
class Solution {
    public int takeAttendance(int[] records) {
        int left = 0 , right = records.length - 1;
        while(left < right){
            int mid = (right - left)/2 + left;
            if(records[mid] == mid){
                left = mid + 1;
            }
            else{
                right = mid;
            }    
        }

        if(records[left] == left){
                left = left + 1;
        }
        return left;
    }
}

0 赞同 0 条回复

=.= 普通 2024年3月30日下午3:19

class Solution {
public int takeAttendance(int[] records) {
int n = records.length;

    int left = 0;
    int right = n - 1;

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

    return left;
}

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

0 赞同 0 条回复

南梁陈庆之普通 2024年3月23日上午2:03

二分查找，匹配中间的数据是否与下标相等

class Solution {
    public int takeAttendance(int[] records) {

        int l = 0, r = records.length - 1;

        while (l <= r) {
            int m = (r - l + 1) / 2 + l;
            if (records[m] == m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return l;
    }
}

0 赞同 0 条回复

NULL 普通 2024年3月22日上午12:32

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 条回复

kfaebot 普通 2024年3月20日上午11:26

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left=0;
        int right=records.size()-1;

        //找到第一个元素值不等于元素索引的元素
        while(left<right){
            int middle=(left+right)/2;

            if(records[middle]==middle){
                left=middle+1;
            }
            else{
                right=middle;
            }
        }
        if(records[left]==left){
            return left+1;
        }
        return left;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月18日下午7:30

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

    }
    return l;
}

思路：找到下标和值不同的那个数据

0 赞同 0 条回复

RunAsOne 普通 2024年3月18日下午4:27

时间复杂度O(logN)

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

0 赞同 0 条回复

一个达不刘普通 2024年3月18日下午4:03

class Solution {
public:
int takeAttendance(vector& records) {
int lhs = 0;
int rhs = records.size()-1;//定义右数组
while(lhs <= rhs){
int mid = (rhs +lhs) / 2;
if(mid records[mid]){
lhs = mid +1;
}else {
rhs = mid-1;
}
}
return lhs;

};

0 赞同 0 条回复

Jimmy 普通 2024年3月18日下午1:21

空间复杂度log(n)，空间复杂度O(1)

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0;
        int right = records.size()-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(records[mid] == mid){// 判断元素与索引的值是否一致
                left = mid + 1;// 一致（因为是升序排列的，该元素一致前面的元素也一致），说明缺失的数字在当前索引的右边
            }else{
                right = mid - 1;// 不一致，说明缺失的数字可能是当前索引对应的值或者在它的左边
            }
        }
        // 当左边界与右边界相等时，可能已经指向该缺失的数字，但是还有一种可能是缺失的数字在数组之外
        // 即[0,1,2]，缺少3，长度为3，即n=4，数的范围0~3
        // return nums[right] != right ? right : right + 1;
        return left;//一定是返回left,跳出时，变量 left 和 right 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素
    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月17日下午9:20

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

       // return records[l];
        return records[l] == l ? l + 1 : l;
    }
}

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

0 赞同 0 条回复

神经蛙普通 2024年3月16日下午11:22

class Solution {
public:
int takeAttendance(vector& records) {
int i = 0, j = records.size() – 1;
while(i < j) {
int m = i + (j – i) / 2;
if(records[m] m) i = m + 1;
else j = m – 1;
}
return records[i] i ? i + 1 : i;
}
};
打卡

0 赞同 0 条回复

mpweixin用户普通 2024年3月16日下午10:10

java
class Solution{
public int countTarget(int[] scores, int target){
return helper(scores, target) – helper(scores, target – 1);
}
int helper(int[] scores, int tar){
int i = 0, j = scores.length – 1;
while(i <= j){
int m = (i + j) / 2;
if(scores[m] <= tar) i = m + 1;
else j = m – 1;
}
return i;
}
}
提交

0 赞同 0 条回复

方铎码农普通 2024年3月16日下午6:57

class Solution {
    public int takeAttendance(int[] records) {
        int l = 0, r = records.length - 1;
        //并非传统意义的二分法，算是双指针找不对劲
        while(l < r){
            int mid = (l+r)/2;
            if(records[mid] == mid) l = mid + 1;
            else r = mid;
        }
        return records[l] == l?records.length:l;
    }
}

时间复杂度O(log(n))，空间复杂度O(1)，注意边界条件，题目假定一定有人没来，即如果0~n-1都齐了，没到的一定是第n个

0 赞同 0 条回复

机电皮怪永久会员 2024年3月16日上午11:52

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

“`C++
class Solution {
public:
int takeAttendance(vector& records) {
int left = 0;
int right = records.size() – 1;
//特殊情况
if(records.empty() == true)
{
return 0;
}
if(records[0] != 0)
{
return 0;
}
if(records[right] != right + 1)
{
return right + 1;
}

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

};

“`

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月16日上午8:51

打卡

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int l = 0, r = records.size() - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(records[mid] == mid) l = mid + 1; // 但凡相等，说明缺失的学号一定在mid右边
            else r = mid - 1; // 但凡不相等，说明缺失的学号在r的mid的左边
        }
        return l;
    }
};

0 赞同 0 条回复

heathhou 普通 2024年3月15日下午10:28

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int l = 0;
        int r = records.size() - 1;

        while(l < r){
            int mid = (r - l) / 2 + l;
            if(records[mid] == mid){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        // 如果缺少最后一个元素，需要返回最后一个元素
        return records[l] == l ? l+1 : l;
    }
};

0 赞同 0 条回复

紫芝普通 2024年3月15日下午9:36

思路：寻找第一个records[idx] > idx的位置，返回idx即可。

“`c++
class Solution {
public:
// 寻找第一个 val > 对应下标
int takeAttendance(vector& records) {
int len = records.size();
int start = 0, end = len – 1, mid;
while (start <= end) { mid = (start + end) / 2; if (records[mid] == mid) start = mid + 1; else end = mid - 1; } return start; } }; ```

0 赞同 0 条回复

言之命至普通 2024年3月15日下午9:29

class Solution {
    public int takeAttendance(int[] records) {
 int l = 0, r = records.length - 1;
        while(l < r){
            int mid = (r - l) / 2 + l;
            if(records[mid] == mid) l = mid + 1; //如果下标和值是一样的，说明在右边
            else r = mid;//否则在左边
        }


//return l  不能直接返回，如果一整个数组都是完整 的数组，说明缺席的数字是最后一个数
        return records[l] == l ? l + 1 : l;

    }
}

0 赞同 0 条回复

MARS 普通 2024年3月15日下午7:50

/**
 * @param {number[]} records
 * @return {number}
 */
var takeAttendance = function(records) {// 找到第一个索引和值不相等的数 
    let left = 0 ,right = records.length-1
    while(left<=right){
        let mid = Math.floor((left+right)/2)
        if(records[mid] === mid){   //如果索引和值相同，则说明缺口在右侧
            left = mid+1   //mid已经相同了，取mid+1
        }else{  //索引值不同，缺口在左侧
            right = mid-1   //当前mid不等于，right-1  避免循环left==right 
        }
    }
    return left
};

0 赞同 0 条回复

王位詮釋普通 2024年3月15日下午6:43

暴力法：
class Solution {
    public int takeAttendance(int[] records) {
        for(int i=0;i<=records.length;i++){
            if(i==records.length){
                return i;
            }
            if(records[i]!=i){
                return i;
            }else{
                continue;
            }
        }
        return -1;
    }
}
思路：判断是否records[mid]==mid，如果是就继续循环，否则就直接返回mid，另外需要判定是否到了length-1位置的时候，如果到了数组最后仍然满足records[mid]==mid则返回length

二分法：
class Solution {
    public int takeAttendance(int[] records) {
        return partial(records,0,records.length-1);
    }
    public int partial(int[] records,int l,int r){
        while(l<r){
            int mid = l+(r-l)/2;
            if(records[mid]!=mid){
                r = mid;
            }else if(records[mid]==mid){
                l = mid+1;;
            }
        }
        if(records[l]!=l){
            return l;
        }else{
            return l+1;
        }
    }
}
思路：如果records[mid] = mid 则表示缺席的编号是在mid后面，所以让 L = mid+1，如果records[mid]!=mid（特指大于，学号大于等于数组下标），则说明缺席编号是在mid及mid之前，所以让 r=mid，当退出循环的时候L和 r 会指向同一位置，如果records[L]==L则说明此时L指向的是数组尾部，且缺席的是L+1，如果records[L]!=L则表示此处就是缺席编号。
时间复杂度：二分遍历数组，O(logn)
空间复杂度：最多是用的是mid，O(1)

0 赞同 0 条回复

Raphtalia. 普通 2024年3月15日下午4:16

class Solution {
public:
int takeAttendance(vector& records) {
int l = 0, r = records.size() – 1;
while(l <= r){
int mid = (l + r) / 2;
if(records[mid] mid) l = mid + 1;
else r = mid – 1;
}
return l;
}
};
时间复杂度O（logn），空间复杂度O（1）

0 赞同 0 条回复

云无深雁影普通 2024年3月15日下午3:22

class Solution {
public int takeAttendance(int[] records) {
int begin = 0;
int end = records.length – 1;
while(begin <= end){
int mid = (begin + end) / 2;
if(records[mid] != mid) end = mid – 1;
else begin = mid + 1;
}
return begin;
}
}
//时间复杂度Ologn
//空间复杂度O1

0 赞同 0 条回复

Yuki 永久会员 2024年3月15日上午11:02

打卡
https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/solutions/2688232/lcr-173-dian-ming-by-yukislab-ltfl

0 赞同 0 条回复

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

共以下 23 个回答

# 回答此问题取消回复

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

共以下 23 个回答

# 回答此问题 取消回复

# 回答此问题取消回复