解题思路
1.知识点
方法一：枚举
思路与算法
我们可以顺序枚举。
枚举法
由于数组是严格递增的，所以可以认为一个不缺失的数组是从1开始的：nums = [1,2,3,4,...].我们可以从头遍历arr数组，并以不缺失数组为基准进行对比，具体来说：
初始化基准 pivot = 1，并令i = 1从头遍历数组arr。
若当前arr[i] == pivot，说明当前i位置之前都不缺元素，继续向后遍历i++，
否则说明缺失正整数pivot，用一个变量count记录已经找到的缺失个数，count++，直到找到第k个缺失的正整数。变量注解
var count = 0 // 缺失个数
var pivot = 1 // 当前应该出现的数
var index = 0 // 数组指针
2.代码
object Solution {
def findKthPositive(arr: Array[Int], k: Int): Int = {
var count = 0
var pivot = 1
var index = 0
while (count<k){
if(arr(index)==pivot){
if((index+1<arr.length)){
index = index+1
}else index = index
} else count=count+1
pivot=pivot+1
}
return pivot-1
}
}
3.复杂度
- 时间复杂度： O(n+k), n是数组长度，k是最坏情况下遍历完数组还没有缺失，则还需要再对count累加k次.
- 空间复杂度： O(1)，仅使用常数空间
