Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数nums[i]以及一些query q[j],输出ans[j]表示从nums[i]中可以最多选择几个数使得加和不超过q[j]。
仔细想想就发现虽然题目中说nums顺序不可交换,但因为可以随意取一些跳过一些,所以其实顺序并不影响,所以先对nums排序,然后预处理prefix sum,之后对于每个查询q[j],二分prefix sum,看最多可以取多少个数,用python自带的二分函数依旧更快一些

用python自带函数

 1 #2389
 2 #Runtime: 86 ms (Beats 97.67%)
 3 #Memory: 13.9 MB (Beats 29.7%)
 4 
 5 class Solution(object):
 6     def answerQueries(self, nums, queries):
 7         """
 8         :type nums: List[int]
 9         :type queries: List[int]
10         :rtype: List[int]
11         """
12         nums.sort()
13         sums = [nums[0]]
14         for i in range(1, len(nums)):
15             sums.append(sums[-1] + nums[i])
16         ans = []
17         for q in queries:
18             ans.append(bisect_right(sums, q))
19         return ans


手写二分:

 1 #2389
 2 #Runtime: 93 ms (Beats 95.35%)
 3 #Memory: 13.8 MB (Beats 56.98%)
 4 
 5 class Solution(object):
 6     def answerQueries(self, nums, queries):
 7         """
 8         :type nums: List[int]
 9         :type queries: List[int]
10         :rtype: List[int]
11         """
12         nums.sort()
13         sums = [nums[0]]
14         for i in range(1, len(nums)):
15             sums.append(sums[-1] + nums[i])
16         ans = []
17         for q in queries:
18             l = 0
19             r = len(nums)
20             while l < r:
21                 mid = (l + r) // 2 
22                 if sums[mid] > q:
23                     r = mid
24                 else:
25                     l = mid + 1
26             ans.append(l)
27         return ans

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