Python C++計數速解Leetcode 945 Minimum Increment to Make Array Unique

Python C++計數速解Leetcode 945  Minimum Increment to Make Array Unique

先計數每個x出現幾次，再從小而大，把多餘的x移動到下一個數字x+1

Python解答請進

-------------

count the frequency for each x , then go from small to large, and move the excess x to the next number x+1

[codes on Leetcode]https://leetcode.com/problems/minimum-increment-to-make-array-unique/solutions/5309906/counting-in-linear-time-43ms-beats-100/

[Leetcode程式]https://www.youtube.com/watch?v=dybiq3pg-Os&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

[Python C++使用prefix sum mod k + hash map解Leetcode523 Continuous Subarray Sum]https://youtu.be/QSO7-Vh87Os?si=LGn0_9TogfNXImP4

Let's consider the testcase nums=[3,2,1,2,1,7,7,7,7,7] see how the freq table works (modified from Python version)

x =  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,
freq[0, 2, 2, 1, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  1:[0, 1, 3, 1, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  2:[0, 1, 1, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  3:[0, 1, 1, 1, 2, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  4:[0, 1, 1, 1, 1, 1, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  7:[0, 1, 1, 1, 1, 1, 0, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0]
  8:[0, 1, 1, 1, 1, 1, 0, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0]
  9:[0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0]
 10:[0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        x0, M=min(nums), max(nums)
        n=len(nums)
        freq=[0]*(M+n)
 
        for x in nums:
            freq[x]+=1
        
        cnt, inc=0, 0
        x=x0
        for x in range(x0, n+M):
            f=freq[x]
            cnt+=(f!=0)
            if f<= 1: continue
        #   freq[x]=1 # for output 
            freq[x+1]+=(f-1)
            inc+=(f-1)
            if cnt>=n-1: break
 
        return inc