Diferencia mínima entre el máximo y el mínimo de todos los subconjuntos de tamaño K

Dada una array de valores enteros, necesitamos encontrar la diferencia mínima entre el máximo y el mínimo de todos los subconjuntos de longitud K posibles.

Ejemplos: 

Input : arr[] = [3, 5, 100, 101, 102]
        K = 3
Output : 2

Explanation : Possible subsets of K-length with
their differences are,
[3 5 100]  max min diff is (100 - 3) = 97
[3 5 101]  max min diff is (101 - 3) = 98
[3 5 102]  max min diff is (102 - 3) = 99
[3 100 101]  max min diff is (101 - 3) = 98
[3 100 102]  max min diff is (102 - 3) = 99
[3 101 102]  max min diff is (102 - 3) = 98
[5 100 101]  max min diff is (101 - 5) = 96
[5 100 102]  max min diff is (102 - 5) = 97
[5 101 102]  max min diff is (102 - 5) = 97
[100 101 102] max min diff is (102 - 100) = 2
As the minimum difference is 2, it should 
be the answer for given array.

Input : arr[] = {5, 1, 10, 6}
        k = 2
Output : 1

We get the above result considering subset
{5, 6}

Podemos resolver este problema sin iterar sobre todos los subconjuntos posibles observando el hecho de que nuestro subconjunto de resultados siempre será consecutivo, una vez que ordenemos la array dada. La razón es que la clasificación reúne elementos cercanos en cuanto a valor. 

Podemos probar el hecho anterior de la siguiente manera: supongamos que elegimos el número a1, a2, a3 … aK que están en orden creciente pero no continuo, entonces nuestra diferencia será (aK – a1) pero si incluimos el número que no se tomó antes ( sea ​​aR), entonces nuestro subconjunto de longitud K será a2, a3, … aR, …. Alaska. En este caso, nuestra diferencia será (aK – a2) que debe ser menor que (aK – a1) porque a2 > a1. Entonces podemos decir que el subconjunto que contendrá nuestra respuesta siempre será consecutivo en una array ordenada. 

Comenzando por el hecho anterior, para resolver el problema primero ordenamos la array, luego iteraremos sobre los primeros (N – K) elementos y cada vez tomaremos la diferencia entre los elementos que están K distantes y nuestra respuesta final será mínima de ellos.

Implementación:

C++

// C++ program to find minimum difference
// between max and min of all subset of K size
#include <bits/stdc++.h>
 
using namespace std;
 
// returns min difference between max
// and min of any K-size subset
int minDifferenceAmongMaxMin(int arr[], int N, int K)
{
    // sort the array so that close
    // elements come together.
    sort(arr, arr + N);
 
    // initialize result by a big integer number
    int res = INT_MAX;
 
    // loop over first (N - K) elements
    // of the array only
    for (int i = 0; i <= (N - K); i++)
    {
        // get difference between max and
        // min of current K-sized segment
        int curSeqDiff = arr[i + K - 1] - arr[i];
        res = min(res, curSeqDiff);
    }
 
    return res;
}
 
// Driver code
int main()
    {
        int arr[] = {10, 20, 30, 100, 101, 102};
        int N = sizeof(arr) / sizeof(arr[0]);
 
        int K = 3;
         cout << minDifferenceAmongMaxMin(arr, N, K);
        return 0;
    }

Java

// Java program to find minimum difference
// between max and min of all subset of
// K size
import java.util.Arrays;
 
class GFG
{
     
    // returns min difference between max
    // and min of any K-size subset
    static int minDifferenceAmongMaxMin(int arr[],
                                    int N, int K)
    {
         
        // sort the array so that close
        // elements come together.
        Arrays.sort(arr);
     
        // initialize result by
        // a big integer number
        int res = 2147483647;
     
        // loop over first (N - K) elements
        // of the array only
        for (int i = 0; i <= (N - K); i++)
        {
             
            // get difference between max and
            // min of current K-sized segment
            int curSeqDiff = arr[i + K - 1] - arr[i];
            res = Math.min(res, curSeqDiff);
        }
     
        return res;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {10, 20, 30, 100, 101, 102};
        int N = arr.length;
     
        int K = 3;
        System.out.print(
            minDifferenceAmongMaxMin(arr, N, K));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to find minimum
# difference between max and min
# of all subset of K size
 
# Returns min difference between max
# and min of any K-size subset
def minDifferenceAmongMaxMin(arr, N, K):
 
    # sort the array so that close
    # elements come together.
    arr.sort()
 
    # initialize result by a
    # big integer number
    res = 2147483647
 
    # loop over first (N - K) elements
    # of the array only
    for i in range((N - K) + 1):
         
        # get difference between max and min
        # of current K-sized segment
        curSeqDiff = arr[i + K - 1] - arr[i]
        res = min(res, curSeqDiff)
     
    return res
     
# Driver Code
arr = [10, 20, 30, 100, 101, 102]
N = len(arr)
K = 3
print(minDifferenceAmongMaxMin(arr, N, K))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to find minimum difference
// between max and min of all subset of
// K size
using System;
 
class GFG
{
     
    // returns min difference between max
    // and min of any K-size subset
    static int minDifferenceAmongMaxMin(int []arr,
                                    int N, int K)
    {
         
        // sort the array so that close
        // elements come together.
        Array.Sort(arr);
     
        // initialize result by
        // a big integer number
        int res = 2147483647;
     
        // loop over first (N - K) elements
        // of the array only
        for (int i = 0; i <= (N - K); i++)
        {
             
            // get difference between max and
            // min of current K-sized segment
            int curSeqDiff = arr[i + K - 1] - arr[i];
            res = Math.Min(res, curSeqDiff);
        }
     
        return res;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr= {10, 20, 30, 100, 101, 102};
        int N = arr.Length;
     
        int K = 3;
    Console.Write(
            minDifferenceAmongMaxMin(arr, N, K));
    }
}
 
// This code is contributed by nitin mittal

PHP

<?php
// PHP program to find minimum difference
// between max and min of all subset
// of K size
 
// returns min difference between max
// and min of any K-size subset
function minDifferenceAmongMaxMin($arr, $N,
                                        $K)
{
    $INT_MAX = 2;
     
    // sort the array so that close
    // elements come together.
    sort($arr); sort($arr , $N);
 
    // initialize result by a
    // big integer number
    $res = $INT_MAX;
 
    // loop over first (N - K) elements
    // of the array only
    for ($i = 0; $i <= ($N - $K); $i++)
    {
         
        // get difference between max and
        // min of current K-sized segment
        $curSeqDiff = $arr[$i + $K - 1] -
                               $arr[$i];
        $res = min($res, $curSeqDiff);
    }
 
    return $res;
}
 
    // Driver Code
    $arr = array(10, 20, 30, 100, 101, 102);
    $N = sizeof($arr);
 
    $K = 3;
    echo minDifferenceAmongMaxMin($arr, $N, $K);
     
// This code is contributed by Nitin Mittal.
?>

Javascript

<script>
 
// JavaScript program to find minimum difference
// between max and min of all subset of
// K size
 
    // returns min difference between max
    // and min of any K-size subset
    function minDifferenceAmongMaxMin(arr, N, K)
    {
         
        // sort the array so that close
        // elements come together.
        arr.sort((a, b) => a - b);
     
        // initialize result by
        // a big integer number
        let res = 2147483647;
     
        // loop over first (N - K) elements
        // of the array only
        for (let i = 0; i <= (N - K); i++)
        {
             
            // get difference between max and
            // min of current K-sized segment
            let curSeqDiff = arr[i + K - 1] - arr[i];
            res = Math.min(res, curSeqDiff);
        }
     
        return res;
    }
 
// Driver Code
 
     let arr = [10, 20, 30, 100, 101, 102];
        let N = arr.length;
     
        let K = 3;
        document.write(
            minDifferenceAmongMaxMin(arr, N, K));
 
</script>
Producción

2

Complejidad de tiempo: O(n Log n)

Este artículo es una contribución de Utkarsh Trivedi . 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. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *