等差数列中缺失的数字

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

在某个数组 arr 中，值符合等差数列的数值规律：在 0 <= i < arr.length - 1 的前提下，arr[i+1] - arr[i] 的值都相等。

我们会从该数组中删除一个 既不是第一个 也 不是最后一个的值，得到一个新的数组 arr。

给你这个缺值的数组 arr，返回 被删除的那个数 。

示例 1：

输入：arr = [5,7,11,13]
输出：9
解释：原来的数组是 [5,7,9,11,13]。

示例 2：

输入：arr = [15,13,12]
输出：14
解释：原来的数组是 [15,14,13,12]。

提示：

3 <= arr.length <= 1000
0 <= arr[i] <= 10⁵
给定的数组保证是一个有效的数组。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int missingNumber(vector<int>& arr) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-15 19:22:33

func missingNumber(arr []int) int {
    n := len(arr)
    d := (arr[n-1] - arr[0])/n
    if d == 0 {
        return arr[0]
    }
    for i := 1; i < len(arr); i++ {
        if arr[i] - arr[i-1] != d {
            return arr[i-1] + d
        }
    }
    return -1
}

python3 解法, 执行用时: 40 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-15 19:22:11

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        d = (arr[-1] - arr[0])//len(arr) #由于收尾肯定不是缺失的数，因此可以计算出公差d
        l = 0
        r = n-1
        while l<=r:  #利用二分的思想
            mid = (l+r)>>1
            if mid+1<n: #限定范围
                if arr[mid+1]-arr[mid] !=d:
                    return arr[mid]+d
            elif mid-1>0:#限定范围
                if arr[mid]-arr[mid-1] !=d:
                    return arr[mid-1]+d
            
            if arr[mid]-arr[l] == (mid-l)*d: #说明在[mid,r]中 
                l = mid+1
            else: # 那么一定在说明在[l,mid]中 
                r = mid-1
        return arr[r]+d

java 解法, 执行用时: 0 ms, 内存消耗: 40 MB, 提交时间: 2023-10-15 19:21:41

class Solution {
   public int missingNumber1(int arr[]) {
       int n = arr.length;

       // 1. 获取差值 `difference`.
       int difference = (arr[n - 1] - arr[0]) / n;
       int lo = 0;
       int hi = n - 1;

       // 二分查找模版。
       while (lo < hi) {
           int mid = (lo + hi) / 2;

           // 所有数字中没有遗漏的数字，所以在右边搜索。
           if (arr[mid] == arr[0] + mid * difference) {
               lo = mid + 1;
           }

           // ‘mid`前缺少一个数字，包括 `mid` 本身。
           else {
               hi = mid;
           }
       }

       // 索引 `lo` 将是第一个数字错误的位置。
       // 返回应该位于此索引处的值。
       return arr[0] + difference * lo;
   }


   public int missingNumber(int[] arr) {
       int n = arr.length;

       // 获取差值 `difference`.
       int difference = (arr[arr.length - 1] - arr[0]) / n;

       // 预期元素等于起始元素。
       int expected = arr[0];

       for (int val : arr) {
           // 返回与val不匹配的期望值。
           if (val != expected) return expected;

           // 下一个元素将是预期元素+`difference`。
           expected += difference;
       }
       return expected;
   }
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 8.2 MB, 提交时间: 2023-10-15 19:21:15

class Solution {
public:
    // 线性搜索
   int missingNumber1(vector<int> &arr) {
       int n = arr.size();

       // 1. 获取差值 `difference`.
       int difference = (arr.back() - arr.front()) / n;

       // 2. 预期元素等于起始元素。
       int expected = arr.front();

       for (int &val : arr) {
           // 返回与val不匹配的期望值。
           if (val != expected) return expected;

           // 下一个元素将是预期元素+`difference`。
           expected += difference;
       }
       return expected;
   }

    // 二分搜索
   int missingNumber(vector<int> &arr) {
       int n = arr.size();

       // 获取差值 `difference`.
       int difference = (arr.back() - arr.front()) / n;
       int lo = 0;
       int hi = n - 1;

       // 二分查找模版。
       while (lo < hi) {
           int mid = (lo + hi) / 2;

           // 所有数字中没有遗漏的数字，所以在右边搜索。
           if (arr[mid] == arr.front() + mid * difference) {
               lo = mid + 1;
           }

           // ‘mid`前缺少一个数字，包括 `mid` 本身。
           else {
               hi = mid;
           }
       }

       // 索引 `lo` 将是第一个数字错误的位置。
       // 返回应该位于此索引处的值。
       return arr.front() + difference * lo;
   }
};

上一题

下一题

详情