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
}

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