Maximizar la diferencia de enteros en un subarreglo de tamaño K

Dado un arreglo arr[] de longitud N, la tarea es encontrar la máxima diferencia de enteros en un subarreglo de tamaño K.

Entrada: arr = [2, 3, -1, -5, 4, 0], K = 3
Salida: 9
Explicación: El subarreglo [-1, -5, 4] contiene la diferencia máxima entre -5 y -4 como 9

Entrada: arr = [-2, -4, 0, 1, 5, -6, 9], K =4
Salida: 15
Explicación: El subarreglo [1, 5, -6, 9] contiene la diferencia máxima entre -6 y 9 como 15

 

Enfoque: el problema dado se puede resolver utilizando la técnica de dos punteros y el enfoque de ventana deslizante con estructura de datos TreeMap . Se pueden seguir los siguientes pasos para resolver el problema:

  • Itere la array arr hasta K – 1 e inserte los elementos en el TreeMap,  
    • Si el número entero ya está presente en el TreeMap, aumente su frecuencia en 1
  • Itere la array arr desde K hasta el final de la array usando un puntero a la derecha y en cada iteración:
    • Inserte el elemento en el TreeMap, si no existe o aumente su frecuencia en 1
    • Retire el elemento más a la izquierda de la ventana deslizante si su frecuencia es uno, o reduzca su frecuencia en 1
    • Calcule la diferencia entre los elementos máximo y mínimo recuperando el primer y el último elemento del treeMap, y también actualice la resolución del resultado.
  • Devuelve el resultado res

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// maximum difference in integers
// of subarray of size K
int maxDiffK(
    vector<int> arr, int K)
{
 
    // Initialize length of the array
    int N = arr.size();
 
    // Initialize a TreeMap
    map<int, int> tm;
 
    // Iterate the array arr till K - 1
    for (int i = 0; i < K; i++)
    {
 
        // Get the frequency of the
        // arr[i] from the treemap
        int f = tm[arr[i]];
 
        // If freq is null
        if (f == 0)
        {
 
            // Add the integer in the
            // treemap with frequency 1
            tm[arr[i]] = 1;
        }
        else
        {
 
            // Increment the frequency
            // of the element
            tm[arr[i]] = f + 1;
        }
    }
 
    // Initialize MaxDiff to the absolute
    // Difference between greatest and
    // smallest element in the treemap
    int maxDiff = abs(
        tm.begin()->first - tm.rbegin()->first);
 
    // Iterate the array arr
    // from K till the end
    for (int i = K; i < N; i++)
    {
 
        // Get the frequency of the
        // current element from the treemap
        int f = tm[arr[i]];
 
        // If freq is null then add the
        // integer in the treemap
        // with frequency 1
        if (f == 0)
        {
 
            tm[arr[i]] = 1;
        }
        else
        {
 
            // Increment the frequency
            // of the element
            tm[arr[i]] = f + 1;
        }
 
        int freq = tm[arr[i - K]];
 
        // If freq is 1 then remove the
        // value from the treemap
        if (freq == 1)
            tm.erase(tm.find(arr[i - K]));
 
        // Else reduce the frequency
        // of that element by 1
        else
            tm[arr[i - K]] = freq - 1;
 
        // Update maxDiff with the maximum
        // of difference between smallest
        // and greatest element in treemap
        // and maxDiff
        maxDiff = max(
            maxDiff,
            abs(
                tm.begin()->first - tm.rbegin()->first));
    }
 
    // Return the answer as maxDiff
    return maxDiff;
}
 
// Driver code
int main()
{
 
    // Initialize the array
    vector<int> arr = {2, 3, -1, -5, 4, 0};
 
    // Initialize the value of K
    int K = 3;
 
    // Call the function and
    // print the result
    cout << (maxDiffK(arr, K));
    return 0;
}
 
// This code is contributed by Potta Lokesh

Java

// Java implementation for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the
    // maximum difference in integers
    // of subarray of size K
    public static int maxDiffK(
        int arr[], int K)
    {
 
        // Initialize length of the array
        int N = arr.length;
 
        // Initialize a TreeMap
        TreeMap<Integer, Integer> tm
            = new TreeMap<>();
 
        // Iterate the array arr till K - 1
        for (int i = 0; i < K; i++) {
 
            // Get the frequency of the
            // arr[i] from the treemap
            Integer f = tm.get(arr[i]);
 
            // If freq is null
            if (f == null) {
 
                // Add the integer in the
                // treemap with frequency 1
                tm.put(arr[i], 1);
            }
            else {
 
                // Increment the frequency
                // of the element
                tm.put(arr[i], f + 1);
            }
        }
 
        // Initialize MaxDiff to the absolute
        // Difference between greatest and
        // smallest element in the treemap
        int maxDiff = Math.abs(
            tm.firstKey() - tm.lastKey());
 
        // Iterate the array arr
        // from K till the end
        for (int i = K; i < N; i++) {
 
            // Get the frequency of the
            // current element from the treemap
            Integer f = tm.get(arr[i]);
 
            // If freq is null then add the
            // integer in the treemap
            // with frequency 1
            if (f == null) {
 
                tm.put(arr[i], 1);
            }
            else {
 
                // Increment the frequency
                // of the element
                tm.put(arr[i], f + 1);
            }
 
            int freq = tm.get(arr[i - K]);
 
            // If freq is 1 then remove the
            // value from the treemap
            if (freq == 1)
                tm.remove(arr[i - K]);
 
            // Else reduce the frequency
            // of that element by 1
            else
                tm.put(arr[i - K], freq - 1);
 
            // Update maxDiff with the maximum
            // of difference between smallest
            // and greatest element in treemap
            // and maxDiff
            maxDiff = Math.max(
                maxDiff,
                Math.abs(
                    tm.firstKey()
                    - tm.lastKey()));
        }
 
        // Return the answer as maxDiff
        return maxDiff;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Initialize the array
        int[] arr = { 2, 3, -1, -5, 4, 0 };
 
        // Initialize the value of K
        int K = 3;
 
        // Call the function and
        // print the result
        System.out.println(maxDiffK(arr, K));
    }
}

Python3

# python code for the above approach
 
# Function to find the
# maximum difference in integers
# of subarray of size K
def maxDiffK(arr, K):
 
    # Initialize length of the array
    N = len(arr)
 
    # Initialize a TreeMap
    tm = {}
 
    # Iterate the array arr till K - 1
    for i in range(0, K):
 
        # If freq is null
        if (not (arr[i] in tm)):
 
            # Add the integer in the
            # treemap with frequency 1
            tm[arr[i]] = 1
        else:
 
             # Increment the frequency
             # of the element
            tm[arr[i]] += 1
 
        # Initialize MaxDiff to the absolute
        # Difference between greatest and
        # smallest element in the treemap
    maxDiff = max(list(tm)) - min(list(tm))
 
    # Iterate the array arr
    # from K till the end
    for i in range(K, N):
 
         # If freq is null then add the
         # integer in the treemap
         # with frequency 1
        if (not (arr[i] in tm)):
            tm[arr[i]] = 1
 
        else:
 
             # Increment the frequency
             # of the element
            tm[arr[i]] += 1
 
        freq = tm[arr[i - K]]
 
        # If freq is 1 then remove the
        # value from the treemap
        if (freq == 1):
            del tm[arr[i - K]]
 
            # Else reduce the frequency
            # of that element by 1
        else:
            tm[arr[i - K]] -= 1
 
            # Update maxDiff with the maximum
            # of difference between smallest
            # and greatest element in treemap
            # and maxDiff
        maxDiff = max(maxDiff, max(list(tm)) - min(list(tm)))
 
    # Return the answer as maxDiff
    return maxDiff
 
# Driver code
if __name__ == "__main__":
   
    # Initialize the array
    arr = [2, 3, -1, -5, 4, 0]
 
    # Initialize the value of K
    K = 3
 
    # Call the function and
    # print the result
    print(maxDiffK(arr, K))
 
    # This code is contributed by rakeshsahni

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
 
    // Function to find the
    // maximum difference in ints
    // of subarray of size K
    public static int maxDiffK(int[] arr, int K)
    {
 
        // Initialize length of the array
        int N = arr.Length;
 
        // Initialize a TreeMap
        Dictionary<int, int> tm = new Dictionary<int, int>();
 
        // Iterate the array arr till K - 1
        for (int i = 0; i < K; i++)
        {
 
            // Get the frequency of the
            // arr[i] from the treemap
            if (!tm.ContainsKey(arr[i]))
            {
 
                // Add the int in the
                // treemap with frequency 1
                tm[arr[i]] = 1;
            }
            else
            {
 
                // Increment the frequency
                // of the element
                tm[arr[i]] += 1;
            }
        }
 
        // Initialize MaxDiff to the absolute
        // Difference between greatest and
        // smallest element in the treemap
        int[] keys = tm.Keys.ToArray();
        Array.Sort(keys);
        int maxDiff = Math.Abs(keys.First() - keys.Last());
 
        // Iterate the array arr
        // from K till the end
        for (int i = K; i < N; i++)
        {
 
            // Get the frequency of the
            // current element from the treemap
 
            if (!tm.ContainsKey(arr[i]))
            {
                tm[arr[i]] = 1;
            }
            else
            {
                // Increment the frequency
                // of the element
                tm[arr[i]] += 1;
            }
 
            int freq = tm[arr[i - K]];
 
            // If freq is 1 then remove the
            // value from the treemap
            if (freq == 1)
                tm.Remove(arr[i - K]);
 
            // Else reduce the frequency
            // of that element by 1
            else
                tm[arr[i - K]] = freq - 1;
 
            // Update maxDiff with the maximum
            // of difference between smallest
            // and greatest element in treemap
            // and maxDiff
            keys = tm.Keys.ToArray();
            Array.Sort(keys);
            maxDiff = Math.Max(maxDiff, Math.Abs(keys.First() - keys.Last()));
        }
 
        // Return the answer as maxDiff
        return maxDiff;
    }
 
    // Driver code
    public static void Main()
    {
 
        // Initialize the array
        int[] arr = { 2, 3, -1, -5, 4, 0 };
 
        // Initialize the value of K
        int K = 3;
 
        // Call the function and
        // print the result
        Console.Write(maxDiffK(arr, K));
    }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

<script>
// Javascript code for the above approach
 
// Function to find the
// maximum difference in integers
// of subarray of size K
function maxDiffK(arr, K) {
 
  // Initialize length of the array
  let N = arr.length;
 
  // Initialize a TreeMap
  let tm = new Map();
 
  // Iterate the array arr till K - 1
  for (let i = 0; i < K; i++) {
 
    // Get the frequency of the
    // arr[i] from the treemap
    let f = tm.get(arr[i]);
 
    // If freq is null
    if (!f) {
 
      // Add the integer in the
      // treemap with frequency 1
      tm.set(arr[i], 1);
    }
    else {
 
      // Increment the frequency
      // of the element
      tm.set(arr[i], f + 1);
    }
  }
 
  // Initialize MaxDiff to the absolute
  // Difference between greatest and
  // smallest element in the treemap
  let maxDiff = Math.abs([...tm.keys()].sort((a, b) => a - b)[0] - [...tm.keys()].sort((a, b) => b - a)[0]);
 
  // Iterate the array arr
  // from K till the end
  for (let i = K; i < N; i++) {
 
    // Get the frequency of the
    // current element from the treemap
    let f = tm.get(arr[i]);
 
    // If freq is null then add the
    // integer in the treemap
    // with frequency 1
    if (!f) {
 
      tm.set(arr[i], 1);
    }
    else {
 
      // Increment the frequency
      // of the element
      tm.set(arr[i], f + 1);
    }
 
    let freq = tm.get(arr[i - K]);
 
    // If freq is 1 then remove the
    // value from the treemap
    if (freq == 1)
      tm.delete((arr[i - K]));
 
    // Else reduce the frequency
    // of that element by 1
    else
      tm.set(arr[i - K], freq - 1);
 
    // Update maxDiff with the maximum
    // of difference between smallest
    // and greatest element in treemap
    // and maxDiff
    maxDiff = Math.max(
      maxDiff,
      Math.abs([...tm.keys()].sort((a, b) => a - b)[0] - [...tm.keys()].sort((a, b) => b - a)[0]));
  }
 
  // Return the answer as maxDiff
  return maxDiff;
}
 
// Driver code
 
 
// Initialize the array
let arr = [2, 3, -1, -5, 4, 0];
 
// Initialize the value of K
let K = 3;
 
// Call the function and
// print the result
document.write((maxDiffK(arr, K)))
 
// This code is contributed by Saurabh Jaiswal
 
 
</script>
Producción

9

Complejidad de tiempo: O(N * log K)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por adventuremonki9 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 *