有序数组中的缺失元素~leetcode春季高校编程大赛决赛~python

不念不忘少年蓝@ 2022-02-16 05:39 197阅读 0赞

题目描述：  
给出一个有序数组 `A`，数组中的每个数字都是 **独一无二的**，找出从数组最左边开始的第 `K` 个缺失数字。

> **示例 1：**
> 
>     输入：A = [4,7,9,10], K = 1
>     输出：5
>     解释：
>     第一个缺失数字为 5 。
> 
> **示例 2：**
> 
>     输入：A = [4,7,9,10], K = 3
>     输出：8
>     解释： 
>     缺失数字有 [5,6,8,...]，因此第三个缺失数字为 8 。
> 
> **示例 3：**
> 
>     输入：A = [1,2,4], K = 3
>     输出：6
>     解释：
>     缺失数字有 [3,5,6,7,...]，因此第三个缺失数字为 6 。

> **提示：**
> 
> 1.  `1 <= A.length <= 50000`
> 2.  `1 <= A[i] <= 1e7`
> 3.  `1 <= K <= 1e8`

\----------------------------------------------------------答题区----------------------------------------------------------

计算出数组中的两个值之间的差，与k作差，如果k刚好为0时，说明此时缺失的数字的数量就是要求的数量了，那返回的结果就应该是两个数较大数减1；如果一不小心，两数之间缺了很多，大于了k，我们先用k2保存k的前一个值，然后用小数加上k2就是应该求出的数了；还有一种情况是，把整个数组遍历完，中间的差值算完，还是比k小，那就从循环中跳出了，然后把最后一个数字加上k还剩余的值，就是要求的值。

class Solution:
        def missingElement(self, nums: List[int], k: int) -> int:
            sum=0
            length=len(nums)
    
            for i in range(length-1):
                sum=(nums[i+1]-nums[i]-1)
                k2=k
                k-=sum
                if(k==0):
                    return (nums[i+1]-1)
                if(k<0):
                    return (nums[i]+k2)
    
            return (nums[-1]+k)