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;
    }
};


回到顶部