在过去一个月，互联网大厂并未暂缓招聘脚步，仅FLAG就放出近3W个岗位！

大厂这波"突然袭击"，搞得很多人措手不及。

小Z就是其中之一，FB面试前半个月接到通知，搞得他根本没时间刷题，更糟的是，面试中还遇到了原题…

为了应对大厂突然袭击，平日的积累显非常重要。一道FB2021算法面试真题，带你了解FB面试难度：

LintCode 1859 最小振幅

题目描述

给定一个由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

更多题解参考