add q945

yuanguangxin · yuanguangxin · commit 1991c8b37cb1 · 2020-03-24T17:21:46.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/README.md b/README.md
@@ -52,6 +52,7 @@
 
 * [q54_螺旋矩阵](/src/数组操作/q54_螺旋矩阵)
 * [q73_矩阵置零](/src/数组操作/q73_矩阵置零)
+* [q945_使数组唯一的最小增量](/src/数组操作/q945_使数组唯一的最小增量)
 
 ### 栈相关
 
diff --git a/src/数组操作/q945_使数组唯一的最小增量/Solution.java b/src/数组操作/q945_使数组唯一的最小增量/Solution.java
@@ -0,0 +1,28 @@
+package 数组操作.q945_使数组唯一的最小增量;
+
+import java.util.Arrays;
+
+/**
+ * 先排序再遍历一次 o(n*log(n))
+ */
+public class Solution {
+
+    public int minIncrementForUnique(int[] A) {
+        if (A == null || A.length == 0 || A.length == 1) {
+            return 0;
+        }
+
+        int rs = 0;
+        Arrays.sort(A);
+
+        int t = A[0];
+        for (int i = 1; i < A.length; i++) {
+            if (A[i] <= t) {
+                rs = rs + t - A[i] + 1;
+                A[i] = t + 1;
+            }
+            t = A[i];
+        }
+        return rs;
+    }
+}
