1.题目

给定整数数组 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 操作是不能让数组的每个值唯一的。

2.解答

2.1 JAVA代码一

会超时，超时原因：时间复杂度达到O(N2)，空间复杂度O(N)。

 public int minIncrementForUnique(int[] A) {
        int len = A.length;
        if(len==0||len==1){
            return 0;
        }
        int res = 0;
        // [主程序-逻辑]:将遍历过的数据存入set中，每次进行对比，如果重复+1再判断
        Set<Integer> set = new HashSet<>();
        set.add(A[0]);
        for(int i=1;i<len;i++){
            int k = A[i];
            while(set.contains(k)){
                k++;
                res++;
            }
            set.add(k);
        }
        return res;
    }

2.2 JAVA代码二

先继续快排，而后贪心算法，时间复杂度O(NlogN)，空间复杂度O(1)；

 /***
     * 快排交换
     */
    public  int quickSwapSort(int[] array,int begin,int end){
        int i= begin;
        int j = end;
        int k = array[i];
        while(i<j){
            // 从右往左
            while(i<j && array[j]>=k){
                j--;
            }
            if(i<j){
                array[i] = array[j];
                i++;
            }

            // 从左往右
            while(i<j && array[i]<k){
                i++;
            }
            if(i<j){
                array[j] = array[i];
                j--;
            }
        }
        array[i] = k;
        return i;
    }

    /***
     * 快速排序
     */
    public  void quickSort(int[] array,int begin,int end){
        if(begin>end){
            return;
        }
        int i= quickSwapSort(array,begin,end);
        quickSort(array,begin,i-1);
        quickSort(array,i+1,end);

    }
    public int minIncrementForUnique(int[] A) {
        int len = A.length;
        if(len==0||len==1){
            return 0;
        }
        // [主程序-快排]：将数组进行快速排序
        quickSort(A,0,len-1);
        /***
         * [主程序-贪心算法]:
         *  逻辑1：A[i]需要和A[0]到A[i-1]进行对比是否重复
         *  逻辑2：如果重复需要继续A[i]++直到不重复为止
         */
        int res = 0;
        for(int i=1;i<len;i++){
            if(A[i-1]>=A[i]){
                res+=A[i-1]-A[i]+1;
                A[i]=A[i-1]+1;
            }
        }
        return res;
    }