LeetCode 1228. 等差数列中缺失的数字

Categories:

题目描述
思路分析
1. 解法一：二分定位缺失项（推荐）
相似题目

题目描述

✅ 1228. 等差数列中缺失的数字

思路分析

解法一：二分定位缺失项（推荐）

核心思路：

等差数列长度为 n + 1，公差为 (arr[n-1] - arr[0]) / n。

设期望值 expected = arr[0] + i * diff，用二分查找第一个不匹配的位置。

返回该位置的期望值即为缺失数字。

复杂度分析：

时间复杂度：O(log n)，二分查找。

空间复杂度：O(1)。

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        int diff = (arr[n - 1] - arr[0]) / n;

        int left = 0;
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int expected = arr[0] + mid * diff;
            if (arr[mid] == expected) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr[0] + left * diff;
    }
}

func missingNumber(arr []int) int {
    n := len(arr)
    diff := (arr[n-1] - arr[0]) / n

    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        expected := arr[0] + mid*diff
        if arr[mid] == expected {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return arr[0] + left*diff
}

相似题目

题目	难度	考察点
153. 寻找旋转排序数组中的最小值	中等	二分查找
852. 山脉数组的峰顶索引	中等	二分查找
74. 搜索二维矩阵	中等	二分查找
35. 搜索插入位置	简单	二分查找
33. 搜索旋转排序数组	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/48719087