xcode - 从大小为 N 的数组中选择 K 个元素，使得子数组中的最小和最大元素之间的差异最小

Question

如何从数组中选择 K 元素，使得子数组中的最小元素和最大元素之间的差异最小

示例：给定数组

     100 200 20 10 30 32 35 50 60 28 18
     k=4

各种可能的结果

    10 18 20 28
    max-min = 28-10 = 18

    28 30 32 35
    max-min = 35-28 = 7

等等

  So, we will select [28 30 32 35] as the subarray

Answer 1

设数组为 a[1..N]。解决。然后选择子数组 a[i], a[i + 1], ..., a[i + K - 1] , i = 1, ..., N - K + 1，使得 a[i + K - 1] - a[i] 是最小的。您可以在线性时间内完成此操作。由于排序需要O(nlogn)算法的总执行时间O(nlogn)