您好,登錄后才能下訂單哦!
小編給大家分享一下leetcode中如何使數(shù)組唯一的最小增量,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
leetcode 每日一題
使數(shù)組唯一的最小增量
給定整數(shù)數(shù)組 A,每次 move 操作將會(huì)選擇任意 A[i],并將其遞增 1。
返回使 A 中的每個(gè)值都是唯一的最少操作次數(shù)。
示例 1:
輸入:[1,2,2]
輸出:1
解釋:經(jīng)過一次 move 操作,數(shù)組將變?yōu)?[1, 2, 3]。
示例 2:
輸入:[3,2,1,2,1,7]
輸出:6
解釋:經(jīng)過 6 次 move 操作,數(shù)組將變?yōu)?[3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能讓數(shù)組的每個(gè)值唯一的。
提示:0 <= A.length <= 400000 <= A[i] < 40000
思路:
排序后,每個(gè)元素都看看是否有重復(fù)元素,如果沒有重復(fù)元素,就pass,有重復(fù)元素,就+1
排序后,其實(shí)就是前后兩個(gè)元素進(jìn)行比較,如果前者小于或者不等于后者,則繼續(xù),如果后者小于或者等于前者,則需要對元素進(jìn)行處理
class Solution:
def minIncrementForUnique(self, A: List[int]) -> int:
if A is None or len(A) < 1:
return 0
length = len(A)
res = 0
A.sort()
'''
# 每個(gè)元素看列表中是否有重復(fù)元素
# 復(fù)雜度太高,超時(shí)不通過
for i in range(length):
value = A[i]
while self.uniq(A, value) is False:
value = value + 1
res += 1
A[i] = value
return res
'''
# 排序后,只要后面的一個(gè)比前面的一個(gè)大就略過
# 小于等于的話就需要變得比它大
for i in range(1, length):
if A[i] <= A[i-1]:
res += A[i-1] - A[i] + 1
A[i] = A[i-1] + 1 # 加1即可
return res
def uniq(self, A, value):
count = 0
for v in A:
if v == value:
count += 1
if count > 1:
return False
else:
return True
以上是“l(fā)eetcode中如何使數(shù)組唯一的最小增量”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。