問題：給你一個數組A，你選擇其中的一個數字，並把它增加1，這就是一次改動。請問至少需要多少次改動，才能使輸入的數組的所有數字都變得唯一。假設數組中的數字在0到40000之間。例如，輸入數組[3, 2, 1, 2, 1, 7]，我們可以通過6次改動使之變成[3, 4, 1, 2, 5, 7]，由於不存在少於6次的改動，因此輸出6。

分析：這是LeetCode的第945題。

解法一：先排序

我們可以先把數組中的數字按照大小排序。如果有重複的數字，這些重複的數字排序之後將排在一起。由於我們的目標是使數組中所有數字都變成唯一，那麼當某個數字是i的時候，它的下一個數字至少應該是i+1。如果下一個數字小於i+1，我們就需要增加它，增加的次數即為數字與i+1之間的差值。

例如輸入數組[3, 2, 1, 2, 1, 7]，排序之後是[1, 1, 2, 2, 3, 7]。第二個數字和第一個數字重複，因此至少要變成2，需要1次增加。接著第三個數字為2。由於第二個數字已經變成2了，它和第二個數字重複，至少需要變成3，因此也要增加一次。

第三個數字變成3之後，第四個數字至少要變成4（因為我們的目標是讓數組成為一個排序的、不含重複數字的數組），因此需要把第四個數字2增加2次。同理，我們也需要把第五個數字3增加2次變成5。第六個數字7和前面的數字沒有重複，不需要增加。

總結一下，經過6次增加，我們把輸入數組變成了[1, 2, 3, 4, 5, 7]。

下面是這種思路的參考代碼：

由於需要對輸入的數組排序，假設數組的長度為n，那麼時間複雜度是O(nlogn)。

解法二：找出沒有出現的數字

我們換一種思路來看這個問題。輸入的數組中有可能出現重複的數字，如果有數字重複了，我們需要把重複的數字替換成沒有在數組中出現的數字。

例如，在數組[3, 2, 1, 2, 1, 7]中，數字1和2都重複出現了。我們需要把一個1和一個2替換成其他數字使得數組中不含重複的數字。我們應該把重複的那個1替換成什麼數字呢？按照題目的規則，我們只能把重複的數字增加，也就是隻能把1替換成比1大的數字。同時替換之後數組中不能出現重複的數字，因此應該把1替換成數組中沒有的數字。最後，我們希望替換的數字儘可能地小，因為題目求最少的增加次數。這麼分析下來，比1大的最小的沒有出現在數組中的數字是4。為了把數字1替換成數字4，需要增加3次。

同理，我們可以把一個重複的數字2替換成5。為了把數字2替換成數字5，也需要增加3次。因此總共至少需要6次增加，就可以把數組中的所有數字都變成唯一。

按照前面的分析，我們需要知道哪些數字重複了多少次，哪些數字在數組中沒有出現，因此我們需要一個哈希表來統計每個數字出現的次數。由於題目給出了數字出現的範圍（最大值為40000），我們可以用一個數組來模擬哈希表。

我們用一個哈希表統計出每個數字出現的數字之後，可以從小到大逐一掃描這個哈希表，一旦遇到重複的數字，可以在後面找到第一個沒有在數組中出現的數字（出現的次數為0）。下面是這個思路的參考代碼：

在上述代碼中，數組numToCount用來衝擊每個數字出現的次數。變數j是大於i的最小的沒有在數組中出現的數字。

代碼中有三個嵌套的循環，看起來時間複雜度是O(n^3)（n為數組numToCount的長度），實際上時間複雜度是O(n)。這是因為在這三個循環中，每次執行的時候都會增加i，有可能增加j。i和j的取值範圍都在0到n-1之間，因此最多執行2n次，因此時間時間複雜度是O(n)。

推薦閱讀：

相關文章