Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

给定一个按严格递增顺序排序的正整数数组arr和一个整数k。

找出这个数组中丢失的第k个正整数。

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

Idea1 (Worst)最笨的办法

What is the worst case? The given array would be [1,2,...,999,1000] and k is 1000, so the 1000th missing number would be 2000. Therefore the stupidest idea is looping through numbers from 1 to 1000 (number i), if we doesn't found the number i in the given array, we count the number of missing numbers (nthNumber += 1, start with zero), we will find the kth missing number when nthNumber == k, return i-1.

最坏的情况是什么?给定数组为[1,2，...，1000]，k是1000。所以第1000个缺失的数字是2000。因此最愚蠢的想法是遍历数字从1到1000(数字 i),如果我们在给定数组中发现数字i，我们统计第n个缺失第数字(nthNumber + = 1,从0开始),我们会发现当nthNumber = = k是，找到第k个失踪第数字,返回i-1。

       func findKthPositive_1(_ arr: [Int], _ k: Int) -> Int {let result = 0var nthNumb = 0for i in 1...2001{if nthNumb == k{return i-1}if !arr.contains(i){nthNumb += 1}}return result}

Idea2 (聪明的做法)

This time, we don't loop through all numbers (arr.count + k, worst case). Using var last to keep track of previous number checked at arr. We have varialbe remainder, which stands for how many numbers do we still need.The difference = item - last - 1, if diff >= remainder, we stop the loop. Usually, if tow numbers are consecutive, the current number  - previous number - 1 equals to 0. Therefor, the difference doesn't influence the value of remainder. the Finally, we return last + remiander as the nth missing number.

这一次，我们没有遍历所有数字 (最坏情况：遍历所有给定数组中的数字+给定的k个数字)。使用var last来跟踪arr，上次检查的数字。var remainder，表示还需要多少个数。差 = 当前数字-上一个数字- 1，如果diff >=余数，我们停止循环。通常，如果两个数是连续的，那么当前数-先前数- 1等于0。因此，差额不影响余数。最后，我们返回 上一个数字+ remiander作为第n个丢失的数字。

Using [2,3,4,7,11], k = 5 as an example:

以[2,3,4,7,11]为例，k = 5:

item = 2, last = 0, remainder = 5, difference = 1 (we miss 1), remainder - 1 = 4, last =  2

item = 3, last = 3, remainder = 4, differ = 0 (we don't miss any number), remainder - 0 = 4, last = 3

item = 4, last = 3, remainder = 4, differ = 0 (we don't miss any number), remainder - 0 = 4, last = 4

item = 7, last = 4, remainder = 4, differ = 7 - 4 - 1 = 2 (between 4 and 7, we miss number 5,6), remiander - 2 = 2, last 7

item = 11, last = 7,remiander = 2, differ = 11-7-1 = 3 (between 7 and 11, we miss number 8,9,10),

now diff = 7 >= remainder

which means we don't have to completely loop through the remaining numbers, we get the kth missing number by adding last + remainder (last + remainer ==  7+2 = 9)

这意味着我们不需要完全遍历剩下的数，我们通过最后一个数+余数(最后一个+余数== 7+2 = 9)得到第k个丢失的数

        func findKthPositive(_ arr: [Int], _ k: Int) -> Int {var last = 0, remainder = kfor item in arr {let diff = item - last - 1if diff >= remainder { break }remainder -= difflast = item}return last + remainder}