[leetcode] 1539. Kth Missing Positive Number

[leetcode] 1539. Kth missing Positive Number

Description

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.

Example 1:

Input: arr = [2,3,4,7,11], k = 5Output: 9Explanation: 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 = 2Output: 6Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

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

分析

题目的意思是：给你一个递增数组，找出第K个缺省的值。很直接，暴力破解就能够解决，如代码一，找到第K个就行了。我在看别人的解法的时候发现了一个更好的解法，只需要遍历arr数组就行了，每次遍历的时候计算两数之间缺省的值的个数，然后推算出第K个位置，很巧妙哈哈哈。

代码一

class Solution: def findKthPositive(self, arr: List[int], k: int) -> int: i=1 j=0 cnt=0 n=len(arr) res=[] while(cnt=n): res.append(i) i+=1 cnt+=1 return res[-1]

代码二

class Solution: def findKthPositive(self, arr: List[int], k: int) -> int: missing=0 n=len(arr) for i in range(n): if(i==0): missing=arr[i]-1 else: missing+=arr[i]-arr[i-1]-1 if(missing>=k): return arr[i]-(missing-k)-1 return arr[-1]+k-missing return res[-1]

参考文献

​​[LeetCode] Python, single array pass. Time: O(N), Space: O(1)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。