Consultas para contar las ocurrencias del elemento de array máximo en subarreglos a partir de índices dados

Posted on by Rudeus Greyrat

Dados dos arreglos arr[] y q[] que consisten en N enteros, la tarea es para cada consulta q[i] determinar el número de veces que el elemento máximo del arreglo aparece en el subarreglo [q[i], arr[N – 1]] .

Ejemplos:

Entrada: arr[] = {5, 4, 5, 3, 2}, q[] = {1, 2, 3, 4, 5}
Salida: 2 1 1 1 1
Explicación:
Para el primer índice de consulta, comience desde 1 El subarreglo es [5, 4, 5, 3, 2], el valor máximo es 5 y su aparición en el subarreglo es 2.
Para el segundo índice de consulta, comience desde 2. El subarreglo es [4, 5, 3, 2] , el valor máximo es 5 y su aparición en el subarreglo es 1.
Para el tercer índice de consulta, comience desde 3. El subarreglo es [5, 3, 2], el valor máximo es 5 y su aparición en el subarreglo es 1.
Para el cuarto el índice de consulta comienza desde 4. El subarreglo es [3, 2], el valor máximo es 3 y su ocurrencia en el subarreglo es 1.
Para el quinto índice de consulta comienza desde 5. El subarreglo es [2], el valor máximo es 2 y su ocurrencia en el subarreglo es 1.

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

Enfoque ingenuo: el enfoque más simple es recorrer la array y encontrar el elemento máximo de la array . Ahora, para cada consulta q[i], recorra el subarreglo [q[i], arr[N – 1]] e imprima el recuento de ocurrencias del elemento máximo en el subarreglo. 

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Hashing . A continuación se muestran los pasos:

  • Cree una array maxFreqVec[] para almacenar la ocurrencia del elemento max del índice dado q[i] a N .
  • Recorra la array arr[] desde la derecha y realice un seguimiento del elemento máximo en la array y actualice la array maxFreqVec[] en ese índice con la aparición de ese elemento máximo.
  • Después de los pasos anteriores, recorra el arreglo q[] e imprima el valor maxFreqVec[q[i] – 1] como el elemento máximo en cada subarreglo para cada consulta.

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

C++

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find occurrence of
// max element in given subarray
void FreqOfMaxElement(vector<int> arr,
                      vector<int> q)
{
     
    // Store the frequency of maximum
    // element
    vector<int> maxFreqVec(arr.size());
 
    int maxSoFar = INT_MIN;
    int maxFreq = 0;
 
    // Traverse over the array arr[]
    // from right to left
    for(int i = arr.size() - 1; i >= 0; i--)
    {
         
        // If curr element is greater
        // than maxSofar
        if (arr[i] > maxSoFar)
        {
             
            // Reset maxSofar and maxFreq
            maxSoFar = arr[i];
            maxFreq = 1;
        }
 
        // If curr is equal to maxSofar
        else if (arr[i] == maxSoFar)
        {
             
            // Increment the maxFreq
            maxFreq++;
        }
 
        // Update maxFreqVec[i]
        maxFreqVec[i] = maxFreq;
    }
 
    // Print occurrence of maximum
    // element for each query
    for(int k : q)
    {
        cout << maxFreqVec[k - 1] << " ";
    }
}
 
// Driver Code
int main()
{
    vector<int> arr = { 5, 4, 5, 3, 2 };
    vector<int> q = { 1, 2, 3, 4, 5 };
     
    // Function Call
    FreqOfMaxElement(arr, q);
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to find occurrence of
    // max element in given subarray
    static void FreqOfMaxElement(
        int[] arr, int[] q)
    {
 
        // Store the frequency of maximum
        // element
        int[] maxFreqVec
            = new int[arr.length];
 
        int maxSoFar = Integer.MIN_VALUE;
        int maxFreq = 0;
 
        // Traverse over the array arr[]
        // from right to left
        for (int i = arr.length - 1;
             i >= 0; i--) {
 
            // If curr element is greater
            // than maxSofar
            if (arr[i] > maxSoFar) {
 
                // Reset maxSofar and maxFreq
                maxSoFar = arr[i];
                maxFreq = 1;
            }
 
            // If curr is equal to maxSofar
            else if (arr[i] == maxSoFar) {
 
                // Increment the maxFreq
                maxFreq++;
            }
 
            // Update maxFreqVec[i]
            maxFreqVec[i] = maxFreq;
        }
 
        // Print occurrence of maximum
        // element for each query
        for (int k : q) {
            System.out.print(
                maxFreqVec[k - 1] + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 5, 4, 5, 3, 2 };
        int[] q = { 1, 2, 3, 4, 5 };
 
        // Function Call
        FreqOfMaxElement(arr, q);
    }
}

Python3

# Python3 program for
# the above approach
import sys;
 
# Function to find occurrence
# of max element in given
# subarray
def FreqOfMaxElement(arr, q):
   
    # Store the frequency of
    # maximum element
    maxFreqVec = [0] * (len(arr));
 
    maxSoFar = -sys.maxsize;
    maxFreq = 0;
 
    # Traverse over the array
    # arr from right to left
    for i in range(len(arr)-1,
                   -1, -1):
 
        # If curr element is
        # greater than maxSofar
        if (arr[i] > maxSoFar):
 
            # Reset maxSofar
            # and maxFreq
            maxSoFar = arr[i];
            maxFreq = 1;
 
        # If curr is equal to
        # maxSofar
        elif (arr[i] == maxSoFar):
 
            # Increment the
            # maxFreq
            maxFreq += 1;
 
        # Update maxFreqVec[i]
        maxFreqVec[i] = maxFreq;
 
    # Print occurrence of maximum
    # element for each query
    for i in range(0, len(q)):
        print(maxFreqVec[q[i] - 1],
              end = " ");
 
# Driver Code
if __name__ == '__main__':
   
    arr = [5, 4, 5, 3, 2];
    q = [1, 2, 3, 4, 5];
 
    # Function Call
    FreqOfMaxElement(arr, q);
 
# This code is contributed by shikhasingrajput

C#

// C# program for the
// above approach
using System;
class GFG{
     
// Function to find occurrence of
// max element in given subarray
static void FreqOfMaxElement(int[] arr,
                             int[] q)
{
  // Store the frequency of
  // maximum element
  int[] maxFreqVec = new int[arr.Length];
 
  int maxSoFar = Int32.MinValue;
  int maxFreq = 0;
 
  // Traverse over the array arr[]
  // from right to left
  for (int i = arr.Length - 1;
           i >= 0; i--)
  {
    // If curr element is greater
    // than maxSofar
    if (arr[i] > maxSoFar)
    {
      // Reset maxSofar and maxFreq
      maxSoFar = arr[i];
      maxFreq = 1;
    }
 
    // If curr is equal to maxSofar
    else if (arr[i] == maxSoFar)
    {
      // Increment the maxFreq
      maxFreq++;
    }
 
    // Update maxFreqVec[i]
    maxFreqVec[i] = maxFreq;
  }
 
  // Print occurrence of maximum
  // element for each query
  foreach (int k in q)
  {
    Console.Write(maxFreqVec[k - 1] +
                  " ");
  }
}
     
// Driver code
static void Main()
{
  int[] arr = {5, 4, 5, 3, 2};
  int[] q = {1, 2, 3, 4, 5};
 
  // Function Call
  FreqOfMaxElement(arr, q);
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find occurrence of
// max element in given subarray
function FreqOfMaxElement(arr, q)
{
     
    // Store the frequency of maximum
    // element
    var maxFreqVec = new Array(arr.length);
    var maxSoFar = -1000000000;
    var maxFreq = 0;
 
    // Traverse over the array arr[]
    // from right to left
    for(var i = arr.length - 1; i >= 0; i--)
    {
         
        // If curr element is greater
        // than maxSofar
        if (arr[i] > maxSoFar)
        {
             
            // Reset maxSofar and maxFreq
            maxSoFar = arr[i];
            maxFreq = 1;
        }
 
        // If curr is equal to maxSofar
        else if (arr[i] == maxSoFar)
        {
             
            // Increment the maxFreq
            maxFreq++;
        }
 
        // Update maxFreqVec[i]
        maxFreqVec[i] = maxFreq;
    }
 
    // Print occurrence of maximum
    // element for each query
    q.forEach(k => {
        document.write( maxFreqVec[k - 1] + " ");
    });
}
 
// Driver Code
var arr = [ 5, 4, 5, 3, 2 ];
var q = [ 1, 2, 3, 4, 5 ];
 
// Function Call
FreqOfMaxElement(arr, q);
 
// This code is contributed by rutvik_56
 
</script>
Producción: 

2 1 1 1 1

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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