使数组唯一的最小增量
程序员文章站
2022-03-03 18:58:13
LeetCodeQuestion.945使数组唯一的最小增量给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。返回使 A 中的每个值都是唯一的最少操作次数。思路1:暴力法求解原本想通过哈希表(hash_map)记录每一个元素的出现次数,通过循环操作使得哈希表的每一个key值对应的value值都为1。但鄙人还是too young too simple,完全忽略时间复杂度的需求,导致运行超时。class Solution(object): def minIncre...
使数组唯一的最小增量
给定整数数组 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