长大后想做什么？做回小孩！

0%

LeetCode——使数组唯一的最小增量

发表于 分类于 Valine：
本文字数： 393

NO.945 使数组唯一的最小增量 中等

84kEqS.png

思路一：排序

非递减排序，然后顺序遍历同时记录出现过的最大值curMax。

如果A[i]大于curMax因为是排序过的数组则A[i]是[0,i]区间内唯一的不需要move；如果A[i]小于等于curMax则需要move增加至大于curMax才能确保A[i]在[0,i]区间内是唯一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minIncrementForUnique(int[] A) {
    if (A.length<2)return 0;
    //排序
    Arrays.sort(A);
    int ans=0,curMax=A[0];
    //遍历
    for (int i = 1; i < A.length; i++) {
        //A[i]小于等于curMax,需要增加到大于curMax
        if (A[i]<=curMax){
            ans+=curMax-A[i]+1;
            A[i]=curMax+1;
        }
        //更新curMax
        curMax=Math.max(curMax,A[i]);
    }
    return ans;
}

时间复杂度：O(nlogn) 排序的时间。

思路二：计数法

有点像计数排序的感觉。计数数组大小为40000*2防止最坏情况40000个39999。

先统计所有数出现的个数。

然后遍历计数数组，如果A[i]个数大于1则将多出来的元素各进行一次move保证A[i]唯一，并将进行move的多余元素个数计入counter[A[i]+1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minIncrementForUnique(int[] A) {
    if (A.length<2)return 0;
    int ans=0;
    //统计数量
    int[] counter=new int[80000];
    for (int i : A) {
        counter[i]++;
    }
    for (int i = 0; i < counter.length; i++) {
        //如果当前元素数量大于1，则将多余元素都分别move后都计入增加后的位置
        if (counter[i] > 1) {
            ans+=counter[i]-1;
            counter[i+1]+=counter[i]-1;
        }
    }
    return ans;
}

时间复杂度：O(n+k) n数组长度，k范围，本题可以看做范围是个常数，复杂度O(n)。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github