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

youngsir 普通 2024年12月21日上午11:13

打卡

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int l = 0,r = records.size()-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 条回复

Renasc 普通 2024年12月15日下午4:45

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

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年12月10日下午11:06

解题思路
– 因为数据都是从0开始，1递增的。通过比较值和下标是否相等就能鉴别异常数据在哪一侧了
【题解1】

class Solution {
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 只有可能大于，那么缺少的点在左边(这个判断只适用于0~n数字能和index映射的)
            if (records[mid] > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 【错误点1】当前节点的值并不是缺少的值，而是当前值-1才是缺少的，没在数组中的
        // 【错误点2】判断+1还是-1,[0,1,2,3,5] 和[1，2,3,4]
        // 应该是根据下标来判断
        return records[left] > left ? records[left] - 1 : records[left] + 1;
    }
}

错误点1：当前节点的值并不是缺少的值，而是当前值-1或者+1才是缺少的，没在数组中的
错误点2：一般情况下是+1，但是如果第一个元素就缺失就是-1了

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午8:41

思路：使用二分查找若record[mid] < mid 说明缺失发生在前半部反之

class Solution {
    public int takeAttendance(int[] records) {
        // 使用 二分 
        // 若缺席 位于 前半部分 则 mid < len+1 反之

        int len = records.length;
        int left = 0;
        int right  = len - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (records[mid] != mid) {
                // 前半段缺失
                right = mid - 1;
            } else {
                // 后半段缺失
                left = mid + 1;
            }
        }

        return left;

    }
}

0 赞同 0 条回复

黑键〰普通 2024年12月10日下午3:55

/**
 * @param {number[]} records
 * @return {number}
 */
var takeAttendance = function(records) {
    let left = 0
    let right = records.length - 1
    while(left <= right) {
        let mid = left + Math.floor((right - left)/2)
        if(records[mid] != mid) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
};

思路：二分查找比较值与下标，不相等则说明缺失的数字在此区间内，找到第一个出现不相等的区间边界即可

0 赞同 0 条回复

Jerry 普通 2024年12月8日下午9:16

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

    }
};

时间o(logn)
空间o1

0 赞同 0 条回复

Kisara 普通 2024年12月6日下午11:11

二分，l和r 若arr[mid]mid说明缺的在右边，l=mid+1，反之r=mid-1

Solution {
    public int takeAttendance(int[] records) {
        int l=0;
        int r=records.length-1;
if(l>r) return 0;

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

}

ologn o1

0 赞同 0 条回复

jaron 普通 2024年12月6日下午9:59

class Solution {
    public int takeAttendance(int[] records) {
        int l = 0, r = records.length - 1, m = 0;
        while(l <= r){
            m = l + (r - l) / 2;
            if(records[m] == m){
                // 说明左边没问题
                l = m + 1;
            }else{
                // 说明左边有问题
                r = m - 1;
            }
        }
        return l;
    }
}

0 赞同 0 条回复

晓宇普通 2024年12月6日下午7:12

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        // 判断下标和值相等，则该序号之前都未缺失；否则缺失
        if(records.empty()) return -1;
        int l = 0, r = records.size() - 1, mid;
        while(l < r){
            mid = (r - l) / 2 + l;
            if(records[mid] == mid){
                l = mid + 1;  // 返回第一个大于下标的元素
            }else if(records[mid] != mid){
                r = mid;
            }
        }
        return records[l] == l ? l + 1 : l;  // 特殊情况: [0] ，即 1 缺席

    }
};
// 时间复杂度:o(lg n)；空间复杂度:o(1)

0 赞同 0 条回复

Aatorx 永久会员 2024年12月6日下午3:58

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

二分查找第一个下标与值不相等的点即可。
时间复杂度O(logN)，空间复杂度O(1)。

0 赞同 0 条回复

lQl 永久会员 2024年12月6日上午12:35

如果不相等,则向左寻找,如果相等,则向右寻找

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

0 赞同 0 条回复

Xiang. 永久会员 2024年12月5日下午11:53

思路：同样采用划分蓝红数组颜色边界的思想，蓝色为所有records[mid]==mid，即正常排序的同学，红色为非正常排序的同学，所以第一个红色就是缺课的同学，返回红色的第一个值即right。边界情况有两种，一种是全为蓝色，也就是班里最后一位同学缺课，此时right即为records.length，另一种全为红色，也就是第一个同学缺课，此时需要特殊处理即第一个元素不为0时直接返回0
class Solution {
    public int takeAttendance(int[] records) {
        int len=records.length;
        if(records[0]==1) return 0;
        int left=-1;
        int right=records.length;
        int mid=0;
        while(left+1!=right){
            mid=((right-left)/2)+left;
            if(records[mid]==mid) left=mid;
            else right=mid;
        }
        return right;

    }
}
时间复杂度：O（logn）
空间复杂度：O（1）
class Solution {
    public int takeAttendance(int[] records) {
        int len=records.length;
        if(records[0]==1) return 0;
        int left=-1;
        int right=records.length;
        int mid=0;
        while(left+1!=right){
            mid=((right-left)/2)+left;
            if(records[mid]==mid) left=mid;
            else right=mid;
        }
        return right;

    }
}

0 赞同 0 条回复

苯庸普通 2024年12月5日下午7:51

class Solution {
public int takeAttendance(int[] records) {
int l = 0, r = records.length-1;
while(l < r){
int m = (l + r)/2;
if(records[m] m){
l = m+1;
}else if(records[m] > m){
r = m;
}
}
return r records.length – 1 && records[r] r ? r + 1 : r;
}
}
思路：二分比对数组元素和下标
时间：O（lgn）
空间：O（1）

0 赞同 0 条回复

月下足迹普通 2024年12月5日下午7:42

//二分查找数组中不等于坐标值的位置
public int takeAttendance(int[] records) {

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

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

0 赞同 0 条回复

迢迢星野普通 2024年12月5日下午6:46

class Solution {
    /**
     * 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
     * 
     * 方法一：顺序遍历
     *
     * 方法二：二分法
     *      升序数组，可以使用二分法，将数组分为两部分，左子数组：nums[i] == i；右子数组：nums[i] != i
     *      缺少的学号就是 右子数组的首位元素 。使用二分法查找右子数组的首位元素。
     * 
     * 方法三：异或运算
     *      a ^ a = 0; a ^ 0 = a；
     * 
     * @param records
     * @return
     */
    public int takeAttendance1(int[] records) {
        for (int i = 0; i < records.length; i++) {
            if (records[i] != i) {
                return i;
            }
        }
        return records.length;
    }

    public int takeAttendance2(int[] records) {
        int l = 0, r = records.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (records[mid] != mid) {
                // 如果不相等的话，左子数组的末位元素，一定在闭区间 [l, mid - 1] 之间
                r = mid - 1;
            } else {
                // 如果相等的话，右子数组的首位元素，一定在闭区间 [mid + 1, r] 之间
                l = mid + 1;
            }
        }
        // 此时的 l、r 分别指向的是右子数组的首位元素、左子数组的末尾元素。
        return l;
    }

    public int takeAttendance(int[] records) {
        int xor = 0;

        for (int i = 0; i < records.length; i++) {
            xor = xor ^ (i + 1) ^ records[i];
        }
        return xor;
    }
}

思路：顺序遍历、二分法、异或运算
时间复杂度：O(n)、O(logn)、O(n)
空间复杂度：都是 O(1)

0 赞同 0 条回复

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

共以下 15 个回答

# 回答此问题取消回复

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

共以下 15 个回答

# 回答此问题 取消回复

# 回答此问题取消回复