Elija k elementos de array de manera que se minimice la diferencia de máximo y mínimo

Dada una array de n enteros y un número positivo k . Se nos permite tomar cualquier k entero de la array dada. La tarea es encontrar el valor mínimo posible de la diferencia entre el máximo y el mínimo de K números.

Ejemplos: 

Input : arr[] = {10, 100, 300, 200, 1000, 20, 30}
        k = 3
Output : 20
20 is the minimum possible difference between any
maximum and minimum of any k numbers.
Given k = 3, we get the result 20 by selecting 
integers {10, 20, 30}.
max(10, 20, 30) - min(10, 20, 30) = 30 - 10 = 20.

Input : arr[] = {1, 2, 3, 4, 10, 20, 30, 40, 
                                   100, 200}.
        k = 4      
Output : 3

La idea es ordenar la array y elegir k enteros continuos. ¿Por qué continuo? Sean los k enteros elegidos arr[0], arr[1], …arr[r], arr[r+x]…, arr[k-1], todos en orden creciente pero no continuos en la array ordenada. Esto significa que existe un entero p que se encuentra entre arr[r] y arr[r+x],. Entonces, si se incluye p y se elimina arr[0], entonces la nueva diferencia será arr[r] – arr[1] mientras que la diferencia anterior era arr[r] – arr[0]. Y sabemos que arr[0] ≤ arr[1] ≤ … ≤ arr[k-1] por lo que la diferencia mínima se reduce o permanece igual. Si realizamos el mismo procedimiento para otros números similares a p, obtenemos la diferencia mínima.

Algoritmo para resolver el problema: 

1. Ordenar la array.
2. Calcule el máximo (k números) – mínimo (k números) para cada grupo de k enteros consecutivos.
3. Devuelve el mínimo de todos los valores obtenidos en el paso 2.

A continuación se muestra la implementación de la idea anterior: 

// C++ program to find minimum difference of maximum
// and minimum of K number.
#include<bits/stdc++.h>
using namespace std;
 
// Return minimum difference of maximum and minimum
// of k elements of arr[0..n-1].
int minDiff(int arr[], int n, int k)
{
    int result = INT_MAX;
 
    // Sorting the array.
    sort(arr, arr + n);
 
    // Find minimum value among all K size subarray.
    for (int i=0; i<=n-k; i++)
        result = min(result, arr[i+k-1] - arr[i]);
 
    return result;
}
 
// Driven Program
int main()
{
    int arr[] = {10, 100, 300, 200, 1000, 20, 30};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
 
    cout << minDiff(arr, n, k) << endl;
    return 0;
}

// Java program to find minimum difference
// of maximum and minimum of K number.
import java.util.*;
 
class GFG {
     
// Return minimum difference of
// maximum and minimum of k
// elements of arr[0..n-1].
static int minDiff(int arr[], int n, int k) {
    int result = Integer.MAX_VALUE;
 
    // Sorting the array.
    Arrays.sort(arr);
 
    // Find minimum value among
    // all K size subarray.
    for (int i = 0; i <= n - k; i++)
    result = Math.min(result, arr[i + k - 1] - arr[i]);
 
    return result;
}
 
// Driver code
public static void main(String[] args) {
    int arr[] = {10, 100, 300, 200, 1000, 20, 30};
    int n = arr.length;
    int k = 3;
 
    System.out.println(minDiff(arr, n, k));
}
}
 
// This code is contributed by Anant Agarwal.

# Python program to find minimum
# difference of maximum
# and minimum of K number.
 
# Return minimum difference
# of maximum and minimum
# of k elements of arr[0..n-1].
def minDiff(arr,n,k):
    result = +2147483647
  
    # Sorting the array.
    arr.sort()
  
    # Find minimum value among
    # all K size subarray.
    for i in range(n-k+1):
        result = int(min(result, arr[i+k-1] - arr[i]))
  
    return result
 
# Driver code
 
arr= [10, 100, 300, 200, 1000, 20, 30]
n =len(arr)
k = 3
  
print(minDiff(arr, n, k))
 
# This code is contributed
# by Anant Agarwal.

// C# program to find minimum
// difference of maximum and
// minimum of K number.
using System;
 
class GFG {
     
// Return minimum difference of
// maximum and minimum of k
// elements of arr[0..n - 1].
static int minDiff(int []arr, int n,
                   int k)
{
    int result = int.MaxValue;
 
    // Sorting the array.
    Array.Sort(arr);
 
    // Find minimum value among
    // all K size subarray.
    for (int i = 0; i <= n - k; i++)
    result = Math.Min(result, arr[i + k - 1] - arr[i]);
 
    return result;
}
 
// Driver code
public static void Main() {
    int []arr = {10, 100, 300, 200, 1000, 20, 30};
    int n = arr.Length;
    int k = 3;
 
    Console.WriteLine(minDiff(arr, n, k));
}
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find minimum
// difference of maximum and
// minimum of K number.
 
// Return minimum difference
// of maximum and minimum
// of k elements of arr[0..n-1].
function minDiff($arr, $n, $k)
{
    $INT_MAX = 2147483647;
    $result = $INT_MAX ;
 
    // Sorting the array.
    sort($arr , $n);
    sort($arr);
 
    // Find minimum value among
    // all K size subarray.
    for ($i = 0; $i <= $n - $k; $i++)
        $result = min($result, $arr[$i + $k - 1] -
                                       $arr[$i]);
    return $result;
}
 
    // Driver Code
    $arr = array(10, 100, 300, 200, 1000, 20, 30);
    $n = sizeof($arr);
    $k = 3;
    echo minDiff($arr, $n, $k);
     
// This code is contributed by nitin mittal.
?>

<script>
// javascript program to find minimum difference
// of maximum and minimum of K number.
 
    // Return minimum difference of
    // maximum and minimum of k
    // elements of arr[0..n-1].
    function minDiff(arr , n , k) {
        var result = Number.MAX_VALUE;
 
        // Sorting the array.
        arr.sort((a,b)=>a-b);
 
        // Find minimum value among
        // all K size subarray.
        for (i = 0; i <= n - k; i++)
            result = Math.min(result, arr[i + k - 1] - arr[i]);
 
        return result;
    }
 
    // Driver code
     
        var arr = [ 10, 100, 300, 200, 1000, 20, 30 ];
        var n = arr.length;
        var k = 3;
 
        document.write(minDiff(arr, n, k));
 
// This code contributed by gauravrajput1
</script>

20

Complejidad de tiempo: O (nlogn).
Espacio Auxiliar: O(1)

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.