Skip to content

945. Minimum Increment to Make Array Unique

945. Minimum Increment to Make Array Unique

题目: https://leetcode.com/problems/minimum-increment-to-make-array-unique/

难度: Medium

题意：

  1. 给定一个数组
  2. 每次操作，数组中的元素只能+1
  3. 求最少多少次操作，数组中所有元素都不相同

思路：

  • 注意看题意，数组中的元素只能+1，所以数组需要先排序，从小到大，因为小的数处理好，大的数不管怎么+1都不会冲突
  • 从小到大循环，需要操作的只可能是跟前一个相同的，或者比前一个小(因为前一个也有可能跟前前一个相同)，因此我们跟前面一个比较，如果比前面一个大，那么啥事都没，如果跟前一个相同，或者比前一个小，那么我们就把他加到比前面一个数大1即可

解法：

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        sort(A.begin(), A.end());
        int ret = 0;
        for (int i= 1;i < A.size();i++) {
            if (A[i] <= A[i - 1]) {
                ret += A[i - 1] - A[i] + 1;
                A[i] = A[i - 1] + 1;
            }
        }
        return ret;
    }
};
回到顶部