当前位置：
  1. 首页
  2. 剑指offer刷题第七期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第七期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
116 15

共以下 15 个回答

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

# 回答此问题

后才能回答