Leetcode 1228:等差数列中缺失的数字(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1228:等差数列中缺失的数字(超详细的解法!!!)

in leetcode with 0 comment

有一个数组,其中的值符合等差数列的数值规律,也就是说:

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

给你这个缺值的数组 arr,请你帮忙找出被删除的那个数。

示例 1:

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

示例 2:

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

提示:

解题思路

这是个纯数学问题,首先很容易计算公差dif=(arr[-1]-arr[0])//(n+1),其中n表示数组arr的长度。根据等差数列求和公式,如果不缺失元素的话,其和为

那么缺失元素即为$sum(A)-sum(arr)$。

class Solution:
    def missingNumber(self, A: List[int]) -> int:
        return (A[0] + A[-1]) * (len(A) + 1) // 2 - sum(A)

但是上面的解法还不是最快的。这是一个查找问题,我们可以使用二分法。我们需要查找缺失元素的位置,然后通过公差和首项即可计算元素的值。那么此时的l=1,而r=n-1。判断mid=l+r>>1对应的元素是不是满足A[mid]=A[0]+d*mid,如果满足,那么在[mid+1,r]这个区间内继续查找;否则,在[l,mid]这个区间内查找。

class Solution:
    def missingNumber(self, A: List[int]) -> int:
        n = len(A)
        d = (A[-1] - A[0]) // n
        l, r = 1, n - 1
        while l < r:
            mid = l + r >> 1
            if A[mid] == A[0] + d * mid:
                l = mid + 1
            else:
                r = mid
        return A[0] + d * l

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses