[leetcode/lintcode 題解]國内大廠高頻面試題： 最小振幅

描述

給定一個由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