Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
 给出一列数,找出p对数字(每个数只能最多用一次),问这p对数字两两之差之和最小多少,直接二分结果,若想两两之差小,那么就是sort之后每次选相邻的数


 1 #2616
 2 #Runtime: 831 ms (Beats 100%)
 3 #Memory: 25.4 MB (Beats 100%)
 4 
 5 class Solution(object):
 6     def minimizeMax(self, nums, p):
 7         """
 8         :type nums: List[int]
 9         :type p: int
10         :rtype: int
11         """
12         n = len(nums)
13         nums.sort()
14         l, r = 0, nums[-1] - nums[0]
15 
16         def cal(dif):
17             nt = 0
18             i = 1
19             while i < len(nums):
20                 if nums[i] - nums[i - 1] <= dif:
21                     i += 1
22                     nt += 1
23                 i += 1
24             return nt
25 
26         while l < r:
27             mid = (l + r) // 2
28             if cal(mid) >= p:
29                 r = mid
30             else:
31                 l = mid + 1
32         return l

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