🔗 945. Minimum Increment to Make Array Unique 1448

tags: `Weekly Contest 112` `貪心(Greedy)` `排序(Sorting)` `計數(Counting)`

題意

給定一個整數陣列 $nums$ 。

在每次操作中，可以選擇一個滿足 $0 \leq i < \text{nums.length}$ 的索引 $i$ ，並將 $\text{nums}[i]$ 增加 $1$ 。

返回使 $\text{nums}$ 中每個值都不同所需的最小操作次數。

約束條件

$1 \leq \text{nums.length} \leq 10^5$
$0 \leq \text{nums[i]} \leq 10^5$
測試案例產生的答案皆在 $32$ 位元整數的範圍內。

思路

方法一：貪心(Greedy) + 排序(Sorting)

首先來看一個比較直覺的方法，由於在每次操作中都只能使某個位置變大，且所求的答案和原本陣列中的元素位置無關。因此可以將陣列由小到大排序後，從左到右遍歷，對於每個位置 $i$ ，如果 $\text{nums}[i] \leq \text{nums}[i-1]$ ，則為了使陣列中的元素不重複，需要將 $\text{nums}[i]$ 調整到 $\text{nums}[i-1] + 1$ ，並將增加的次數加到答案中。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，排序需要 $\mathcal{O}(n \log n)$ 的時間，遍歷排序後的陣列需要 $\mathcal{O}(n)$ 的時間。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序所需的空間。

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        ans = 0
        for i in range(1, n):
            if nums[i] <= nums[i-1]:
                ans += nums[i-1] + 1 - nums[i]
                nums[i] = nums[i-1] + 1
        return ans

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i-1]) {
                ans += nums[i-1] + 1 - nums[i];
                nums[i] = nums[i-1] + 1;
            }
        }
        return ans;
    }
};

方法二：計數(Counting)

注意到約束條件中的 $\text{nums[i]} \leq 10^5$ ，且 $\text{nums.length} \leq 10^5$ ，因此在最差情況下，操作後的元素值可能會達到 $10^5 + 10^5 = 2 \times 10^5$ ，因此可以使用基於值域的計數方法。

維護一個長度為 $2 \times 10^5$ 的陣列 $cnt$ ，其中 $cnt[i]$ 表示數字 $i$ 出現的次數。遍歷值域中的每個數字 $x$ ， $x$ 出現次數大於 $1$ ，則代表有 $cnt[x] - 1$ 個 $x$ 需要被調整成更大的數字，因此先把這些多餘的數字加到一個陣列 $left$ 中。當遇到下一個數字時，如果該數字沒有出現過，則可以從 $left$ 中取出一個多餘的數字，將其調整到當前數字，並將答案加上需要的操作次數。

雖然直接使用長度為 $2 \times 10^5$ 的陣列也能通過，但是為了節省空間，可以先找出最大值 $mx$ ，由於最差情況下為 $nums$ 中的所有元素皆為 $mx$ ，因此操作完成後的值域為 $[0, mx + n)$ ，故使用一個長度為 $mx + n$ 的陣列即可。

複雜度分析

時間複雜度： $\mathcal{O}(mx + n)$ $O (m x + n)$ ，其中 $n$ $n$ 是陣列 $nums$ $n u m s$ 的長度， $mx$ $m x$ 是陣列中的最大值。
- 遍歷陣列 $nums$ 需要 $\mathcal{O}(n)$ 的時間。
- 遍歷 $cnt$ 陣列需要 $\mathcal{O}(mx + n)$ 的時間。
空間複雜度： $\mathcal{O}(mx + n)$ ，使用了長度為 $mx + n$ 的陣列 $cnt$ ，以及長度最大為 $O(n)$ 的陣列 $left$ 。

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        n = len(nums)
        mx = max(nums)
        cnt = [0] * (mx + n)
        for x in nums:
            cnt[x] += 1
        ans = 0
        left = []
        for x in range(mx + n):
            if cnt[x] >= 2:
                left.extend([x] * (cnt[x] - 1))
            elif left and cnt[x] == 0:
                ans += x - left.pop()
        return ans

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        int n = nums.size(), mx = *max_element(nums.begin(), nums.end());
        vector<int> cnt(mx + n, 0), left;
        for (int x : nums) cnt[x]++;
        int ans = 0;
        for (int x = 0; x < mx + n; x++) {
            if (cnt[x] >= 2) {
                left.insert(left.end(), cnt[x] - 1, x);
            } else if (!left.empty() && cnt[x] == 0) {
                ans += x - left.back();
                left.pop_back();
            }
        }
        return ans;
    }
};

方法二優化

在方法二中，我們需要使用一個陣列 $left$ 來存放多餘的數字，使得在每次遇到新的數字時，需要從 $left$ 中取出一個數字。這裡可以進一步優化，不需要使用 $left$ 陣列，只需要維護一個整數 $left\_cnt$ 來表示多餘的數字個數即可。

由於枚舉到沒有出現過的數字 $x$ 時，需要從 $left$ 中取出一個數字 $y$ ，將 $y$ 調整到 $x$ ，此時需要的操作次數為 $x - y$ 。可以看出若 $cnt[y] \geq 2$ ，則其對答案的貢獻為 $-y \times (cnt[y] - 1)$ ，因此可以提前計算 $y$ 的貢獻，並將其加到答案中。如此便不用維護 $left$ 陣列。

但在枚舉值域中的數字時，仍然需要紀錄前面是否出現過多餘的數字，因此需要維護一個整數 $left\_cnt$ 來表示多餘的數字個數。

複雜度分析

時間複雜度： $\mathcal{O}(mx + n)$ $O (m x + n)$ ，其中 $n$ $n$ 是陣列 $nums$ $n u m s$ 的長度， $mx$ $m x$ 是陣列中的最大值。
- 遍歷陣列 $nums$ 需要 $\mathcal{O}(n)$ 的時間。
- 遍歷 $cnt$ 陣列需要 $\mathcal{O}(mx + n)$ 的時間。
空間複雜度： $\mathcal{O}(mx + n)$ ，使用了長度為 $mx + n$ 的陣列 $cnt$ 。

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        n = len(nums)
        mx = max(nums)
        cnt = [0] * (mx + n)
        for x in nums:
            cnt[x] += 1
        ans = 0
        left = 0
        for x in range(mx + n):
            if cnt[x] >= 2:
                left += cnt[x] - 1
                ans -= x * (cnt[x] - 1)
            elif left > 0 and cnt[x] == 0:
                ans += x
                left -= 1
        return ans

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        int n = nums.size(), mx = *max_element(nums.begin(), nums.end());
        vector<int> cnt(mx + n, 0);
        for (int x : nums) cnt[x]++;
        int ans = 0, left = 0;
        for (int x = 0; x < mx + n; x++) {
            if (cnt[x] >= 2) {
                left += cnt[x] - 1;
                ans -= x * (cnt[x] - 1);
            } else if (left > 0 && cnt[x] == 0) {
                ans += x;
                left--;
            }
        }
        return ans;
    }
};