從大小爲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

讓數組成爲[1..N]。把它分類。然後選擇子陣列a [i]，a [i + 1]，...，a [i + K-1]，i = 1，...，N - K + 1，使得[i + K - 1] - a [i]是最小的。你可以在線性時間內做到這一點。由於排序需要O(nlogn)算法的總執行時間爲O(nlogn)