[leetcode/lintcode 题解]国内大厂高频面试题： 最小振幅

描述
给定一个由N个整数组成的数组A，一次移动，我们可以选择此数组中的任何元素并将其替换为任何值。 数组的振幅是数组A中的最大值和最小值之间的差。 返回通过执行最多三次替换之后数组A的最小振幅。

N是一个整数而且范围是: [2, 10000]A数组中的每一个元素都是整数而且范围是: [-50, 50]

在线评测地址：领扣题库官网

样例1
A = [-9, 8, -1]
可以将 -9 和 8 替换成-1，这样所有元素都等于 -1，所以振幅是0

样例 2
A = [14, 10, 5, 1, 0]
为了实现振幅是1，我们可以将 14，10，5 替换成 1 或者 0

样例 3
A = [11, 0, -6, -1, -3, 5]
可以将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

本文转自网络，原文链接：https://developer.aliyun.com/article/784343
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！