Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数,每次将其中最大的数变成第二大的数,问最少几次可以把所有数变成一样,sort然后按不同数字出现次数加和

Time complexity: O(nlogn)
Space complexity: O(1)

 1 #1887
 2 #Runtime: 768 ms (Beats 100%)
 3 #Memory: 19.2 MB (Beats 66.67%)
 4 
 5 class Solution(object):
 6     def reductionOperations(self, nums):
 7         """
 8         :type nums: List[int]
 9         :rtype: int
10         """
11         nums.sort()
12         nt_sum = 0
13         pre = nums[-1]
14         nt = 1
15         ans = 0
16         for i in xrange(len(nums) - 2, -1, -1):
17             if nums[i] == pre:
18                 nt += 1
19             else:
20                 nt_sum += nt
21                 ans += nt_sum
22                 nt = 1
23                 pre = nums[i]
24         return ans

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