別具一格 讓所有數字都相異的最少加法操作 Min Increment Make Array Unique_LC#945

Anna Sullivan on Unsplash

題目敘述 Minimum Increment to Make Array Unique

給定一個整數陣列，每回合可以任意挑一個數字進行+1的加法操作。
請問最少需要多少次的+1加法操作，才能讓每個數字都相異?

測試範例

Example 1:

Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].

2 調整成 3
需要一次加法操作。​

Example 2:

Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

1 調整成 2
第一個2 調整成 3
第二個2 調整成 4
3 調整成 5

總共需要六次加法操作。​

約束條件

Constraints:

• 1 <= nums.length <= 10^5

陣列長度介於1~十萬。

• 0 <= nums[i] <= 10^5

每個陣列元素介於1~十萬。

觀察

每個整數都要相異，相當於把重複的整數重新mapping到更大的整數，
而且為了讓加法操作數目越少越好，重新mapping的距離越近越好，也就是離自己越近越好。

這個過程就相當於hash function中的線性探測linear probing，遇到碰撞時，
重新往右側尋找空的格子，每次往右找一格，一直找到空格子為止。

演算法 線性探測

維護一張hash table，儲存每個整數對應到的格子點。

最理想的情況是 x -> x，映射到原本的位置，這樣就不需要額外加法。

假如遇到碰撞時，也就是重複的整數，往右側尋找空的格子，找到之後，把原本重複的x映射到右側離自己最近的整數，並且計算對應的+1加法操作次數。

程式碼 線性探測

class Solution(object):
    def minIncrementForUnique(self, nums):
        
        # Linear probing to find vacant index in grid
        def findVacant(number, grid):

            vacantIndex = grid[number]
            if vacantIndex == -1:
                grid[number] = number
                return number

            vacantIndex = findVacant(vacantIndex + 1, grid)
            grid[number] = vacantIndex
            return vacantIndex
        # ------------------------------------------------

        # index: integer
        # value: index of vacant grid
        grid = defaultdict(lambda :-1)
        incOperation = 0
        for number in nums:
            vacantIndex = findVacant(number, grid)
            incOperation += vacantIndex - number

        return incOperation

複雜度分析

時間複雜度:O(n)

線性掃描每個整數，每個整數可以在常數時間內找到空的格子。

空間複雜度: O(n)

需要一個Hash table來儲存每個整數被映射到的格子點。

關鍵知識點

每個整數都要相異，相當於把重複的整數重新mapping到更大的整數，

而且為了讓加法操作數目越少越好，重新mapping的距離越近越好，也就是離自己越近越好。

這個過程就相當於hash function中的線性探測linear probing，遇到碰撞時，

重新往右側尋找空的格子，每次往右找一格，一直找到空格子為止。

Reference

[1] Minimum Increment to Make Array Unique - LeetCode