【剑指Offer刷题系列】0～n-1中缺失的数字

问题描述

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

注意：

• records 数组是 升序排列 的。
• 数组中 仅缺少一个学号，且学号范围为 0 到 n-1。

提示：

• 1 <= records.length <= 10^4
• 0 <= records[i] <= 10^4
• records.length = n - 1

原题链接：：点名 。

示例

示例 1：

输入：

records = [0,1,2,3,5]

输出：

4

解释：
学号 4 缺席。

示例 2：

输入：

records = [0, 1, 2, 3, 4, 5, 6, 8]

输出：

7

解释：
学号 7 缺席。

思路解析

本题要求在一个 升序排列 且 仅缺少一个元素 的数组中，找到缺失的学号。由于数组是有序的，可以利用 二分查找 来高效地解决问题。

核心思路：

1. 二分查找：

   • 初始化 left = 0，right = len(records) - 1。
   • 在每一步，计算中间位置 mid。
   • 比较 records[mid] 与 mid：
     • 如果 records[mid] == mid，说明缺失的学号在右半部分，更新 left = mid + 1。
     • 否则，缺失的学号在左半部分（包括 mid），更新 right = mid - 1。
   • 最终，left 即为缺失的学号。

2. 边界情况：

   • 如果所有元素均满足 records[i] == i，则缺失的学号为 n-1。

具体步骤：

1. 初始化：

   • 设置 left = 0，right = len(records) - 1。

2. 二分查找过程：

   • 当 left <= right 时，重复以下步骤：
     • 计算中间位置 mid = left + (right - left) // 2。
     • 如果 records[mid] == mid：
       • 说明缺失的学号在右侧，设置 left = mid + 1。
     • 否则：
       • 说明缺失的学号在左侧或当前 mid，设置 right = mid - 1。

3. 返回结果：

   • 当循环结束时，left 即为缺失的学号。

复杂度分析：

• 时间复杂度：O(log n)，其中 n 是数组 records 的长度。通过二分查找，将搜索范围每次减半。

• 空间复杂度：O(1)。只使用了常数级别的额外空间。

代码实现

Python 实现

from typing import List

class Solution:
    def missingNumber(self, records: List[int]) -> int:
        left, right = 0, len(records) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if records[mid] == mid:
                left = mid + 1
            else:
                right = mid - 1
        return left

测试代码

以下是针对上述方法的测试代码，使用 unittest 框架进行验证。

import unittest

class TestMissingNumber(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_example1(self):
        records = [0,1,2,3,5]
        target = 4
        self.assertEqual(self.solution.missingNumber(records), target, "示例1失败")

    def test_example2(self):
        records = [0,1,2,3,4,5,6,8]
        target = 7
        self.assertEqual(self.solution.missingNumber(records), target, "示例2失败")

    def test_missing_at_beginning(self):
        records = [1,2,3,4,5]
        target = 0
        self.assertEqual(self.solution.missingNumber(records), target, "缺失在开头测试失败")

    def test_missing_at_end(self):
        records = [0,1,2,3,4]
        target = 5
        self.assertEqual(self.solution.missingNumber(records), target, "缺失在结尾测试失败")

    def test_single_element_present(self):
        records = [0]
        target = 1
        self.assertEqual(self.solution.missingNumber(records), target, "单元素存在测试失败")

    def test_single_element_absent(self):
        records = []
        target = 0
        self.assertEqual(self.solution.missingNumber(records), target, "空数组测试失败")

    def test_all_elements_present_except_one_middle(self):
        records = [0,1,2,4,5,6]
        target = 3
        self.assertEqual(self.solution.missingNumber(records), target, "中间缺失测试失败")

    def test_large_array_missing_last(self):
        records = list(range(10000))
        target = 10000
        self.assertEqual(self.solution.missingNumber(records), target, "大数组缺失最后一个测试失败")

    def test_large_array_missing_first(self):
        records = list(range(1, 10001))
        target = 0
        self.assertEqual(self.solution.missingNumber(records), target, "大数组缺失第一个测试失败")

    def test_large_array_missing_middle(self):
        records = list(range(0, 5000)) + list(range(5001, 10001))
        target = 5000
        self.assertEqual(self.solution.missingNumber(records), target, "大数组中间缺失测试失败")

if __name__ == "__main__":
    unittest.main(argv=[''], exit=False)

输出：

..........
----------------------------------------------------------------------
Ran 10 tests in 0.XXXs

OK

复杂度分析

时间复杂度

• 总体复杂度：O(log n)，其中 n 是数组 records 的长度。

  • 采用二分查找，每次将搜索范围减半，直到找到缺失的学号。

空间复杂度

• 总体复杂度：O(1)。

  • 算法只使用了常数级别的额外空间，不依赖于输入规模。

通过采用 二分查找 的方法，我们能够高效地在一个 升序排列 且 仅缺少一个元素 的数组中找到缺失的学号。该方法利用了数组的有序性，通过对比索引与元素值，迅速缩小搜索范围，确保了算法的高效性和正确性。

掌握此类二分查找的应用技巧，对于解决类似的查找问题具有重要的指导意义，能够在实际编程和算法设计中灵活应用，提高代码的性能和效率。