【剑指offer|图解|二分查找】点名 + 统计目标成绩的出现次数

2023-12-14 10:54:31

在这里插入图片描述
🌈个人主页:聆风吟
🔥系列专栏:剑指offer每日一练
🔖少年有梦不应止于心动,更要付诸行动。


一. ??点名

? 在线OJ链接,可以转至此处自行练习 ?

1.1 题目

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席,请返回他的学号。

1.2 示例

输入: records = [0,1,2,3,5]
输出: 4

1.3 限制

  • 1 <= records.length <= 10000

1.4 解题思路一

二分查找
根据题意,数组可以按照以下规则进行划分为两部分:

  • 左子数组:records[i] = i
  • 右子数组:records[i] != i

缺失的数字等于 右子数组的首位元素 对应的索引,因此我们可以使用二分查找右子数组首元素。
在这里插入图片描述

算法执行过程

  1. 初始化 :左边界 l = 0 和 右边界 r = records.size() - 1
  2. 循环二分:当 l <= r 时循环
    • 计算中心点 mid = (l + r) / 2;
    • 如果 records[mid] = mid 说明要查找的值在区间[mid + 1, r] 之间,因此执行 l = mid + 1;
    • 如果 records[mid] != mid 说明要查找的值在区间[l, mid - 1] 之间,因此执行 r = mid - 1;
  3. 返回值:循环跳出时,返回 l 即可。

在这里插入图片描述

c++代码

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int sz = records.size();

        int l = 0;
        int r = sz - 1;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(records[mid] == mid) l = mid + 1;
            else r = mid -1;
        }

        return l;
};

1.5 解题思路二

求和做差
有题目可知:
0 ~ n - 1 之间所有同学的学号加在一起,然后减去数组中的每个元素,所得结果即是缺课人学号。
在这里插入图片描述

c++代码

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        
        int sz = records.size();
        int sum = sz*(sz+1)/2;//使用等差求和公式求全班学号的总和
        
        //将全班人的学号 - 数组中的每一个元素
        for(int i = 0; i < sz; i++)
        {
            sum -= records[i];
        }

        return sum;
    }
};


二. ??统计目标成绩的出现次数

? 在线OJ链接,可以转至此处自行练习 ?

1.1 题目

某班级考试成绩按非严格递增顺序记录于整数数组 scores,请返回目标成绩 target 的出现次数。

1.2 示例

输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3

1.3 限制

  • 0 <= scores.length <= 105
  • -109 <= scores[i] <= 109
  • scores 是一个非递减数组
  • -109 <= target <= 109

1.4 解题思路

对于已经排好序的数组查找问题,首先我们可以想到是用二分查找。

对于排序数组 scores 中所有数字 target 形成一个窗口,记做窗口的 左 / 右边界 索引分别为 left 和 right,分别对应窗口的左右两边。因此本题求数字 target 出现的次数,就可以转化为:使用二分法分别求出窗口的左边界 left 和 右边界 right,容易得出数字 target 出现的次数 right - left + 1。
在这里插入图片描述


1. 查找右边界:

//查找右边界
while(l < r)
{
	int mid = (l + r + 1) >> 1;
    if(scores[mid] <= target) l = mid;
    else r = mid - 1;
}

在这里插入图片描述

注意

  1. 在查找完右边界后,需要用 scores[right] 判断一下数组中是否含有 target,若不包含则直接提前返回 0,无需继续查找左边界
  2. 记得让指针 l,r 重新回到起点处

2. 查找左边界:

//查找左边界
while(l < r)
{
	int mid = (l + r) >> 1;
	if(scores[mid] >= target) r = mid;
	else l = mid + 1;
}

由于左边界的查找同右边界运行类似,大家可以在下面自己画出图形,调试。

c++代码

class Solution {
public:
    int countTarget(vector<int>& scores, int target) {
        int sz = scores.size();
        int l = 0;
        int r = sz - 1;

        // 搜索右边界
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(scores[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int right = r;

        // 若数组中无 target ,则提前返回
        if(r >= 0 && scores[right] != target) return 0;

        // 搜索左边界
        l = 0, r = sz - 1;//让指针返回到初始状态
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(scores[mid] >= target) r = mid;
            else l = mid + 1;
        }
        int left = l;

        return right - left + 1;
    }
};


📝结语

???? 今天的干货分享到这里就结束啦!如果觉得文章还可以的话,希望能给个三连支持一下,聆风吟的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的最大动力!
在这里插入图片描述

文章来源:https://blog.csdn.net/2301_80026901/article/details/134987029
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。