Leetcode 945. Minimum Increment to Make Array Unique

题目

945. Minimum Increment to Make Array Unique

Difficulty: Middle
Total Accepted: 5,139
Total Submissions: 12,879

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Example 1:

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

Example 2:

Input: [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.

Note:

0 <= A.length <= 40000
0 <= A[i] < 40000

解题报告

AC 截图

题目大意

我们有一个可能有重复数字的数组，并且我们可以通过令某些元素 += 1 数次来消除重复。那么这样的操作最少需要多少次呢？

解题思路

由于题目给定了数组的长度和数组的最大长度，我们可以创建一个固定的，满足最大大小的数组，来统计每个数字出现的次数，然后当一个数字出现多次时，我们保留其中的一个，令剩余元素 += 1，如此递归，便能得到最终的解。

题解（最优解）

结果截图

C++ 代码

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

static short A[40000];

class Solution {
public:
    int minIncrementForUnique(vector<int>& As) {
        memset(A, 0, 40000 * sizeof(short));
        int result = 0, maxEle = 0, minEle = 40000;
        
        for (auto &ele : As) {
            ++A[ele];
            maxEle = max(maxEle, ele);
            minEle = min(minEle, ele);
        }
        
        for (int i = minEle; i < maxEle; ++i) {
            if (A[i] > 1) {
                A[i + 1] += A[i] - 1;
                result += A[i] - 1;
            }
        }
        
        if (A[maxEle] > 1) result += (A[maxEle]) * (A[maxEle] - 1) / 2;
        return result;
    }
};