数组中n个元素的最大最小差

Question

给出数组A和数字N。

从阵列A中选择N个元素，以使这N个数字之间的最小差最大。返回最大最小差。

Example1。 A = {1,2,4,8,9}，N = 3

输出： 3 （因为{1,4,9}使这三个数字之间的差最大。4-1 = 3，9-4 = 5）

Example2。 A = {4,1,2,8,90,900}，N = 4

输出： 7

这是数据结构课程中的一个问题，我整天都在为这个问题而苦苦挣扎，希望有人可以帮助我。谢谢！

Answer 1

1. 排序数组
2. 对于N = 2，输出将是[0]和[n]中的值，其中0和n是数组的索引（n是数组的长度）
3. 对于N = 3 0，n和n / 2（如果n为奇数，则需要检查哪个更适合n / 2和n / 2 + 1）并将数组拆分为2
4. 对于N = 4，您需要检查2个数组中哪个“中位数”提供最佳结果。
5. 我想您明白了，总是将每个一半除以2。

复杂度：n * log（n）用于排序+ N（用于校验+拆分）