使数组唯一的最小增量

使数组唯一的最小增量

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。

思路1：暴力法求解

原本想通过哈希表*(hash_map)记录每一个元素的出现次数，通过循环操作使得哈希表的每一个key值对应的value值都为1*。但鄙人还是too young too simple，完全忽略时间复杂度的需求，导致运行超时。

class Solution(object): def minIncrementForUnique(self, A): """
        :type A: List[int]
        :rtype: int
        """ count = 0 hash_map = {} for i in sorted(A): if i not in hash_map: hash_map[i] = 1 else: hash_map[i] += 1 j = 0 while j < len(hash_map.keys()): i = list(hash_map.keys())[j] j+=1 if hash_map[i] == 1: continue else: if i + 1 in hash_map: cnum = hash_map[i] - 1 count += cnum
                    hash_map[i] -= cnum
                    hash_map[i + 1] += cnum else: cnum = hash_map[i] - 1 count += cnum
                    hash_map[i + 1] = cnum
                    hash_map[i] -= cnum return count 

思路2：贪心算法

贪心原则：将数组从小到大进行排序，从第二个元素起每个元素必须大于前一位元素。

定义一个记录操作步数的变量count,每进行一步操作就加1，而每一步的操作次数可以通过 A[i] - A[i-1] + 1式子计算得到

class Solution(object): def minIncrementForUnique(self, A): """
        :type A: List[int]
        :rtype: int
        """ A = sorted(A) count = 0 for i in range(1, len(A)): if A[i] <= A[i - 1]: count += A[i - 1] - A[i] + 1 A[i] += A[i - 1] - A[i] + 1 return count 

此时的时间复杂度主要来源于排序，运行可以通过。

以上仅用于记录学习过程，如果有更好的方法欢迎相互交流讨论！

本文地址：https://blog.csdn.net/weixin_45554388/article/details/109063510