【C++习题】24.二分查找算法_0～n-1中缺失的数字

2025/9/20 21:13:05 来源：https://blog.csdn.net/hlyd520/article/details/144176047 浏览: 次关键词：【C++习题】24.二分查找算法_0～n-1中缺失的数字

文章目录

- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解

题目链接：

剑指 Offer 53 - II. 0～n-1中缺失的数字

题目描述：

fa91c9e0a51f48e60b0424775c039edc

解法

哈希表：

建立一个hash表看哪个数字出现次数为0

直接遍历找结果：

看从哪里断开了，断开的数就是我们要找的数

位运算：

异或运算，拿数组里面的数和完整的数放到一起，相同的会抵消掉。

例如：[0,1,2,4,5]和[0,1,2,3,4,5]

异或后，只剩下3

数学方法：高斯求和公式

先把没缺少的数组求和，利用等差数列公式，然后依次减去原数组的数，得到的结果就是我们缺失的数。

二分算法：

找二段性

d5d4f6a8cf0c0034d67ffccdcd36a8bc

虚线左边和下标一样，右边比下标大一。我们要找的就是虚线右边最左侧的那个数的下标。

C++ 算法代码：

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 right = mid;}return left == records[left] ? left + 1 : left;  }
};