Encuentre la suma de las medianas de todos los subarreglos de longitud impar

Dada una array arr[] de tamaño N , la tarea es encontrar la suma de las medianas de todas las subarreglas de longitud impar.

Ejemplos :

Entrada : arr[] = {4, 2, 5, 1}
Salida : 18
Explicación : las subarrays de longitud impar y sus medianas son:

• [4]  -> La mediana es 4
• [4, 2, 5]  -> La mediana es 4
• [2]  -> La mediana es 2
• [2, 5, 1]  ​​-> La mediana es 2
• [5]  -> La mediana es 5
• [1]  -> La mediana es 1

Su suma = 4 + 4+ 2 + 2 + 5 +1 = 18

Entrada : arr[] = {1, 2}
Salida : 3

Requisitos previos : Mediana de flujo de enteros en ejecución usando STL

Enfoque ingenuo : genera todos y cada uno de los subconjuntos. Si la longitud del subconjunto es impar, ordene el subconjunto y devuelva el elemento central.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find sum of medians
// of all odd-length subarrays
int solve(vector<int> arr)
{
    int ans = 0;
    int n = arr.size();
 
    // Loop to calculate the sum
    for(int i = 0; i < n; i++)
    {
        vector<int> new_arr;
        for(int j = i; j < n; j++)
        {
            new_arr.push_back(arr[j]);
             
            // Odd length subarray
            if ((new_arr.size() % 2) == 1)
            {
                sort(new_arr.begin(), new_arr.end());
                int mid = new_arr.size() / 2;
                ans += new_arr[mid];
            }
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 4, 2, 5, 1 };
    cout << solve(arr);
}
 
// This code is contributed by Samim Hossain Mondal.

// Java program for the above approach
import java.util.*;
 
class GFG {
    // Function to find sum of medians
    // of all odd-length subarrays
    static int solve(int[] arr) {
        int ans = 0;
        int n = arr.length;
 
        // Loop to calculate the sum
        for (int i = 0; i < n; i++) {
            List<Integer> new_arr = new LinkedList<Integer>();
            for (int j = i; j < n; j++) {
                new_arr.add(arr[j]);
 
                // Odd length subarray
                if ((new_arr.size() % 2) == 1) {
                    Collections.sort(new_arr);
                    int mid = new_arr.size() / 2;
                    ans += new_arr.get(mid);
                }
            }
        }
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args) {
        int[] arr = { 4, 2, 5, 1 };
        System.out.println(solve(arr));
    }
}
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function to find sum of medians
# of all odd-length subarrays
def solve(arr):
        ans = 0
        n = len(arr)
         
        # Loop to calculate the sum
        for i in range(n):
            new_arr = []
            for j in range(i, n, 1):
                new_arr.append(arr[j])
 
                # Odd length subarray
                if (len(new_arr)) % 2 == 1:
                    new_arr.sort()
                    mid = len(new_arr)//2
                    ans += new_arr[mid]
        return (ans)
 
# Driver Code
if __name__ == "__main__":
    arr = [4, 2, 5, 1]
    print(solve(arr))
    

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to find sum of medians
  // of all odd-length subarrays
  static int solve(int[] arr) {
    int ans = 0;
    int n = arr.Length;
 
    // Loop to calculate the sum
    for (int i = 0; i < n; i++) {
      List<int> new_arr = new List<int>();
      for (int j = i; j < n; j++) {
        new_arr.Add(arr[j]);
 
        // Odd length subarray
        if ((new_arr.Count % 2) == 1) {
          new_arr.Sort();
          int mid = new_arr.Count / 2;
          ans += new_arr[mid];
        }
      }
    }
    return ans;
  }
 
  // Driver Code
  public static void Main() {
    int[] arr = { 4, 2, 5, 1 };
    Console.Write(solve(arr));
  }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
 
// javascript program for the above approach
    // Function to find sum of medians
    // of all odd-length subarrays
    function solve(arr) {
        var ans = 0;
        var n = arr.length;
 
        // Loop to calculate the sum
        for (var i = 0; i < n; i++) {
            var new_arr= new Array();
            for (var j = i; j < n; j++) {
                new_arr.push(arr[j]);
 
                // Odd length subarray
                if ((new_arr.length % 2) == 1) {
                    new_arr.sort();
                    var mid = Math.floor(new_arr.length / 2);
                     
                    // document.write(mid);
                    ans += new_arr[mid];
                }
            }
        }
        return ans;
    }
 
    // Driver Code
var arr = [ 4, 2, 5, 1 ];
document.write(solve(arr));
 
// This code is contributed by shikhasingrajput
</script>

18

Complejidad de tiempo : O(N ³ * Log(N)) Espacio auxiliar : O(N)  

Nota: En lugar de ordenar la array cada vez, lo que cuesta ( N*logN) , se puede aplicar la ordenación por inserción. Pero aún así, la Complejidad Temporal general será O(N ³ ).

Enfoque eficiente: la mediana de la array ordenada es el valor que separa la mitad superior de la mitad inferior de la array. Para encontrar la mediana, solo necesitamos el elemento central, en lugar de toda la array ordenada. El enfoque de la mediana de la corriente de enteros continuos se puede aplicar aquí. Siga los pasos que se mencionan a continuación 

1. Use pilas máximas y mínimas para calcular la mediana móvil.
2. Atraviesa todos y cada uno de los elementos de la array.
3. Al crear un nuevo subarreglo, agregue un elemento en los montones y devuelva la mediana si el tamaño es impar; de lo contrario, devuelva 0.
4. Max_heap se usa para almacenar los elementos de la mitad inferior , de modo que el elemento máximo esté en la parte superior, y min_heap se usa para almacenar los elementos de la mitad superior , de modo que el elemento mínimo esté en la parte superior.
5. La diferencia entre ambos montones no debe ser mayor que uno, y siempre se coloca un elemento adicional en max_heap .

Nota : aquí max_heap se implementa usando min_heap, simplemente negando los valores para quese pueda extraer el elemento negativo máximo .

A continuación se muestra la implementación del enfoque anterior:  

# Python program for the above approach
from heapq import heappush as push, heappop as pop
 
# Find the sum of medians of odd-length
# subarrays
 
 
class find_median():
 
    # Constructor to declare two heaps
    def __init__(self):
 
        # Store lower half elements such that
        # maximum element is at top
        self.max_heap = []
 
        # Store higher half elements such that
        # minimum element is at top
        self.min_heap = []
 
    def add(self, val):
 
        # len(max_heap) == 0 or curr_element
        # smaller than max_heap top
        if (len(self.max_heap) == 0 or
            self.max_heap[0] > val):
            push(self.max_heap, -val)
 
        else:
            push(self.min_heap, val)
 
        # If size of max_heap + 1 greater
        # than min_heap
        if (len(self.max_heap)+1 >
            len(self.min_heap)):
            val = pop(self.max_heap)
            push(self.min_heap, -val)
 
        # If size of min_heap
        # greater than max_heap
        if (len(self.min_heap) >
            len(self.max_heap)):
            val = pop(self.min_heap)
            push(self.max_heap, -val)
 
        # Finally if sum of sizes is odd,
        # return median
        if (len(self.min_heap) +
            len(self.max_heap)) % 2 == 1:
            return (-self.max_heap[0])
 
        # Else return 0
        else:
            return 0
 
# Function to calculate the sum
# of all odd length subarrays
def solve(arr):
    ans = 0
     
    # Size of the array
    n = len(arr)
    for i in range(n):
         
        # Create an object
        # of class find_median
        obj = find_median()
        for j in range(i, n, 1):
             
            # Add value to the heaps
            # using object
            val = obj.add(arr[j])
            ans += val
     
    return (ans)
 
# Driver Code
if __name__ == "__main__":
    arr = [4, 2, 5, 1]
    print(solve(arr))

18

Complejidad de tiempo : O(N ² * Log(N)) Espacio auxiliar : O(N)