LeetCode945-使数组唯一的最小增量

问题：使数组唯一的最小增量

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

返回使 A 中的每个值都是唯一的最少操作次数。

示例 1:

输入：[1,2,2]

输出：1

解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2:

输入：[3,2,1,2,1,7]

输出：6

解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。

可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

提示：

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

链接：https://leetcode-cn.com/contest/weekly-contest-112/problems/minimum-increment-to-make-array-unique/

分析：

1.每次move会将一个数字值加一

2.最终每个数字都不一样

3.最终结果应该是唯一的

4.增加方式不唯一，但是等价，比如从1 4 变为4 5，可以是1+4，也可以是1+3，4+1

5.操作次数其实就是最终数列和减去初始数列和

那么将原序列排序，要求递增，且差值中至少1，如果本身值就比前一个大于1，则保持，否则增加为前一个数字值+1，统计累计加值即为最终结果。

AC Code：

 class Solution {

 public:

 int minIncrementForUnique(vector<int>& A) {

         int ret = ;

         if (A.size() < )

         {

             return ;

         }

         sort(A.begin(), A.end());

         int pre = A[];

         for (int i = ; i < A.size(); i++)

         {

             if (A[i] <= pre)

             {

                 ret += (pre +  - A[i]);

                 pre += ;

             }

             else

             {

                 pre = A[i];

             }

         }

         return ret;

     }

 };

其他：

第一code：

 typedef long long ll;

 typedef vector<int> VI;

 typedef pair<int,int> PII;

 #define REP(i,s,t) for(int i=(s);i<(t);i++)

 #define FILL(x,v) memset(x,v,sizeof(x))

 const int INF = (int)1E9;

 #define MAXN 100005

 class Solution {

 public:

   int minIncrementForUnique(vector<int>& A) {

     if (A.size() == ) return ;

     sort(A.begin(), A.end());

     int last = A[];

     int ans = ;

     REP(i,,A.size()) {

       if (A[i] <= last) {

         ans += last +  - A[i];

         last++;

       } else {

         last = A[i];

       }

     }

     return ans;

   }

 };

巴特西

LeetCode945-使数组唯一的最小增量

最新文章

热门文章