[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