Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列已经单调递增排序的数列,输出缺失的第K小的数


Input: arr = [2,3,4,7,11], k = 5
Output: 9
Input: arr = [1,2,3,4], k = 2
Output: 6

水题

 1 #1539
 2 #Runtime: 34 ms (Beats 74.54%)
 3 #Memory: 13.5 MB (Beats 56.83%)
 4 
 5 class Solution(object):
 6     def findKthPositive(self, arr, k):
 7         """
 8         :type arr: List[int]
 9         :type k: int
10         :rtype: int
11         """
12         t, p = 0, 0
13         for i in arr:
14             p += 1
15             while p < i:
16                 t += 1
17                 if t == k:
18                     return p
19                 p += 1
20         while t < k:
21             t += 1
22             p += 1
23         return p

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理