给出一列数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