当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.945.Minimum Increment to Make Array Unique 使数组唯一的最小增量

LeetCode.945.Minimum Increment to Make Array Unique 使数组唯一的最小增量

题目描述

945 Minimum Increment to Make Array Unique
https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Example 1:

Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].

Example 2:

Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

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


解题过程

这道题我只会暴力搜索,看了题解后,发现有各种思路,非常灵活,很不错的一道题。

先排序

首先要搞清楚一个性质,把x以步长1递增为y,无论先后步骤数是不变的。
比如 2 和 3 都重复,分别需要提升为比较大的另外两个数,无论他俩谁先提升,最终的步骤数都一样。

O(nlogn) 排序,然后从小到大遍历,遇到重复的,记下来,遇到中间有间隔的,把之前重复的数提升到这个区间内,提升的步骤数就等于区间内的空位对应的值减去记住的重复的数。

这里面要用到一个等差数列求和公式 sn = na1 + n(n-1)d/2 来快速计算。

时间复杂度 O(nlogn),空间复杂度 O(logn),快速排序需要额外 logn 的栈空间。

public int minIncrementForUnique(int[] A) {
    if (null == A || A.length < 2) {
        return 0;
    }
    // 快速排序 nlogn
    Arrays.sort(A);
    // 重复个数
    int duplicateCount = 0;
    // 重复数的和,遇到重复数增加其负值,遇到可用的空位增加正值
    int duplicateSum = 0;
    for (int i = 1; i < A.length; i++) {
        if (A[i] > A[i - 1] + 1 && duplicateCount != 0) {
            // A[i-1] 到 A[i] 之间有 A[i] - A[i-1] - 1 个空位可供使用
            int emptyCount = Math.min(duplicateCount, A[i] - A[i-1] - 1);
            duplicateCount -= emptyCount;
            duplicateSum += emptyCount * (A[i-1] +1) + emptyCount * (emptyCount-1) / 2;
        } else if (A[i] == A[i-1]) {
            duplicateCount++;
            duplicateSum += -A[i];
        }
    }
    // 最后可能有还没处理的重复数
    if (duplicateCount != 0) {
        duplicateSum += duplicateCount * (A[A.length-1] + 1) + duplicateCount * (duplicateCount - 1) / 2;
    }
    return duplicateSum;
}

暴力搜索

把数组元素都放入 map 计数,遇到重复的不断加1直到不再重复。
时间复杂度 O(n^2), 空间复杂度 O(n)

但提交后会超时,遇到超大数组时太慢了,毕竟是一个一个往上加后计算的。

// 暴力,超时
public int minIncrementForUnique_TimeLimitExceed(int[] A) {
    if (null == A || A.length < 2) {
        return 0;
    }

    Map<Integer, Integer> map = new HashMap<>();

    int steps = 0;
    for (int n : A) {
        if (!map.containsKey(n)) {
            map.put(n, 0);
        } else {
            int incr = n + 1;
            while (map.containsKey(incr)) {
                incr++;
            }
            steps += incr - n;
            map.put(incr, 0);
        }
    }
    return steps;
}

GitHub代码

algorithms/leetcode/leetcode/_945_MinimumIncrementToMakeArrayUnique.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_945_MinimumIncrementToMakeArrayUnique.java


上一篇 LeetCode.876.Middle of the Linked List 链表的中间结点

下一篇 LeetCode.365.Water and Jug Problem 水壶问题

阅读
评论
676
阅读预计3分钟
创建日期 2020-03-22
修改日期 2020-03-22
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论