当前位置：首页 > news >正文

二分查找算法(8) _点名

news 2024/11/16 20:43:15

个人主页：C++忠实粉丝
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝原创

二分查找算法(8) _点名

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

温馨提示:

1. 题目链接 :

2. 题目描述 :

3. 解法 :

1. 哈希表

算法思路 :

代码展示 :

结果分析 :

2. 暴力遍历

算法思路 :

代码展示 :

结果分析 :

3. 位运算

算法思路 :

代码展示 :

结果分析 :

4. 数学(高斯求和公式)

算法思路 :

代码展示 :

结果分析 :

5. 二分查找算法

算法思路 :

代码展示 :

结果分析 :

4. 二分算法模板总结

温馨提示:

这道题是直接使用了二分模板,轻松拿捏了这道题,如果你还不知道的话,自行去下篇博客

---二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板-CSDN博客

1. 题目链接 :

OJ链接: 点名

2. 题目描述 :

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

示例 1:

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

示例 2:

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

提示：

1 <= records.length <= 10000

3. 解法 :

1. 哈希表

算法思路 :

算法步骤
1. 初始化数据结构：

        使用 unordered_map<int, int>来记录数组中每个元素的出现次数。
2. 遍历记录：

        遍历给定的 records 数组，对于每个元素 records[i]，将其作为键存入哈希表，并将对应的值（计数）加 1。这样可以快速跟踪数组中每个元素的出现情况。
3. 查找缺失的最小值：

        从 0 开始遍历到 records.size()（包括 size，这是因为缺失的数字可以是等于数组长度的情况）。
        对于每个 i，检查哈希表中是否存在 i 作为键。
        如果 hash[i] 的值为 0，则表示 i 在数组中缺失，立即返回 i。
4. 返回最后的结果：

        如果在 0 到 records.size() 的所有整数中都存在，返回 records.size()，表示下一个缺失的非负整数就是数组的大小。

代码展示 :

class Solution {
public:int takeAttendance(vector<int>& records) {unordered_map<int, int> hash;for(int i = 0; i < records.size(); i++)hash[records[i]]++;for(int i = 0; i <= records.size(); i ++)if(hash[i] == 0) return i;return 0;}
};

结果分析 :

时间复杂度
O(n)：遍历数组一次来构建哈希表，再遍历 0 到 records.size() 进行查找。总的时间复杂度是线性的。
空间复杂度
O(n)：在最坏情况下，哈希表需要存储数组中的所有元素。

2. 暴力遍历

算法思路 :

思路
外层循环：从 0 开始，逐渐检查每个非负整数 i。
内层循环：遍历 records 数组，检查 i 是否存在。
找不到则返回：如果内层循环没有找到 i，则立即返回 i。

代码展示 :

class Solution {
public:int takeAttendance(vector<int>& records) {for(int i = 0; ; i++){bool found = false;for(int j = 0; j < records.size(); j++){if(records[j] == i){found = true;break;}}if(!found) return i;}return -1;}
};

结果分析 :

时间复杂度
O(n ^ 2)：最坏情况下需要检查所有 n 个元素多次，因此时间复杂度为 O(n²)，在数组很大时效率较低。
空间复杂度
O(1)：没有使用额外的数据结构，只是使用了常量空间。

3. 位运算

算法思路 :

算法流程
1. 初始化：

使用变量 ret 初始化为 0，用于存储最终结果。
2. 第一轮循环：

遍历 0 到 n 的所有整数（包括 n）。
将所有整数进行异或操作。
3. 第二轮循环：

遍历输入数组 records 中的元素（从 0 到 n - 1）。
将所有元素进行异或操作。
4. 返回结果：

最后，ret 中的值就是缺失的最小非负整数。

代码展示 :

class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();int ret = 0;for(int i = 0; i <= n; i++){ret ^= i;}for(int i = 0; i <= n - 1; i++){ret ^= records[i];}return ret;}
};

结果分析 :

复杂度分析
时间复杂度：O(N)，算法中有两个循环，各遍历 n 次。
空间复杂度：O(1)，只使用了常量级的额外空间。
关键点
异或的特性：相同的数异或为 0，不同的数异或为 1，因此最后的结果是缺失的数字。
范围：由于 records 中的值在 0 到 n - 1 之间，最终的异或结果会得出缺失的最小非负整数。

4. 数学(高斯求和公式)

算法思路 :

算法流程
初始化：

变量 ret 初始化为从 0 到 n（records.size()）的和，使用公式 n * (n + 1) / 2。这里 n 是 records.size()。
遍历输入数组：

使用范围循环遍历 records 中的每个元素，将其值从 ret 中减去。
返回结果：

最终，ret 中的值就是缺失的最小非负整数。

代码展示 :

class Solution {
public:int takeAttendance(vector<int>& records) {int ret = records.size() * (records.size() + 1) / 2;for(auto ch : records)ret -= ch;return ret;}
};

结果分析 :

复杂度分析
时间复杂度：O(N)，算法中有一个循环遍历 records，因此整体复杂度是线性的。
空间复杂度：O(1)，只使用了常量级的额外空间。
关键点
数学求和：通过计算 0 到 n 的总和，快速得到应有的总和。
缺失的整数：通过减去实际存在的记录值，最终得到缺失的整数。

5. 二分查找算法

算法思路 :

在这个升序的数组中,我们发现:

在第一个缺失位置的左边,数组内的元素都是与数组下标相等的;

在第一个缺失位置的右边,数组内元素与数组下标是不相等的.

因此, 我们可以利用这个[二段性], 来使用[二分查找]算法.

代码展示 :

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) right = mid;else left = mid + 1;}if(records[left] == left) return left + 1;else return records[left] - 1;}
};

1. 初始化：

        定义两个指针 left 和 right，分别指向 0 和 records.size() - 1。
2. 二分搜索：

        进入 while 循环，直到 left 小于 right。
        计算 mid 为(left + (right - left) / 2)，避免溢出。
        检查 records[mid] 是否等于 mid：
                如果 records[mid] 不等于 mid，说明在 mid 左侧的元素缺失，因此将 right 移动到 mid。
                如果 records[mid] 等于 mid，说明在 mid 右侧的元素未缺失，因此将 left 移动到 mid + 1。
3. 返回结果：

        循环结束后，left 将指向第一个缺失的数或最后一个不缺失的数。
        通过检查 records[left] 与 left 的关系：
                如果 records[left] 等于 left，说明缺失的数字是 left + 1。
                否则，返回 records[left] - 1，这表示缺失的数字在 left 的左侧。

结果分析 :

复杂度分析
时间复杂度：O(log N)，由于使用了二分搜索，每次搜索都将查找范围减半。
空间复杂度：O(1)，只使用了常量级的额外空间。
关键点
有序性：算法假设输入数组是已排序的，这对于二分搜索是必要的前提。
边界条件：需要确保涉及数组索引时不越界，并正确处理缺失数字的位置。

4. 二分算法模板总结

这里再次强调一下我们的二分算法模板(真的很好用!!!)

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