给出一列数,每次将其中最大的数变成第二大的数,问最少几次可以把所有数变成一样,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