描述
給定一個由N個整數組成的數組A,一次移動,我們可以選擇此數組中的任何元素并将其替換為任何值。 數組的振幅是數組A中的最大值和最小值之間的差。 傳回通過執行最多三次替換之後數組A的最小振幅。
- N是一個整數而且範圍是: [2, 10000]
- A數組中的每一個元素都是整數而且範圍是: [-50, 50]
線上評測位址:
領扣題庫官網樣例1
輸入:
A = [-9, 8, -1]
輸出:
0
解釋:
可以将 -9 和 8 替換成-1,這樣所有元素都等于 -1,是以振幅是0
樣例 2
輸入:
A = [14, 10, 5, 1, 0]
輸出:
1
解釋:
為了實作振幅是1,我們可以将 14,10,5 替換成 1 或者 0
樣例 3
輸入:
A = [11, 0, -6, -1, -3, 5]
輸出:
3
解釋:
可以将11,-6,5都換成-2
解題思路
将數組進行排序,然後将首尾的值進行相減,判斷內插補點最小值,也可以通過O(n)周遊尋找出最大值、最小值等,但是代碼過于備援,推薦直接排序。
複雜度分析
時間複雜度:O(nlogn)
需要周遊一遍數組,并且排序算法時間複雜度為O(nlogn)。
空間複雜度:O(1)
源代碼
class Solution:
"""
@param A: a list of integer
@return: Return the smallest amplitude
"""
def MinimumAmplitude(self, A):
if len(A) <= 4:
return 0
length = len(A)
A = sorted(A)
mmin = float('inf')
for i in range(4):
mmin = min(mmin, A[length - 3 + i - 1] - A[i])
return mmin
更多題解參考:
九章官網solution