2019LeetCode春季全国高校赛决赛-1. 有序数组中的缺失元素

1. 有序数组中的缺失元素给出一个有序数组 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 <= A.length <= 500001 <= A[i] <= 1e71 <= K <= 1e8

   废话不多说，直接上代码。

   func missingElement(nums []int, k int) int {
       basemap:= map[int]int{}
       step:=0
       targetnums:=0
       for _,v:=range nums{
           basemap[v]++
       }
       for i:=nums[0];k!=step;i++ {
           if _,ok:=basemap[i];ok {
               continue
           }else {
               if i>nums[len(nums)-1] {
                   targetnums=nums[len(nums)-1]+k-step
                   break
               }
               targetnums=i
               step++
           }
       }
       return targetnums
   }
   

   根据题意可知，我们需要从 A[0]开始依次递增 1 至 k 次，在此设递增值为 v,此 v 并不存在于 A 中。

故用 Map 字典法来求 target 值，首先将 nums 改为字典。

for _,v:=range nums{
    basemap[v]++
}

后面从 A[0]为基准依次以 1 为增量递增 i,并判断 i 是否存在于 basemap(即基准 map)中，若存在，则 i++，进入下次循环，直至我们 k 与我们的 step(递增次数相等时，便输出 targetnums.

在这里，这道题有一个脑经急转弯的地方，如果没有好好处理，便会产生资源消耗过多的情况。

假设我们的 i 已经超过了 A 的最后一个元素，那么我们的 k 不就是

K=A[Len(A)-1]+(K-Step)

于是在循环中增加判断

if i>nums[len(nums)-1] {
    targetnums=nums[len(nums)-1]+k-step
    break
}

笔者就是在这里卡顿了将近一个小时，果然还是太菜了啊。。。。