題目敘述 Minimum Increment to Make Array Unique
給定一個整數陣列，每回合可以任意挑一個數字進行+1的加法操作。
請問最少需要多少次的+1加法操作，才能讓每個數字都相異?
測試範例
Example 1:
Input: nums = [1,2,2]Example 2:
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].
2 調整成 3
需要一次加法操作。
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，遇到碰撞時，
重新往右側尋找空的格子，每次往右找一格，一直找到空格子為止。
