Maximice el recuento de K elementos únicos que se pueden elegir de Array

Dada una array arr[] de tamaño N y una array de consultas Q[] de tamaño M, donde Q[i] define el recuento de elementos únicos que deben elegirse de la array arr[]. La tarea de encontrar el número máximo de elementos que se pueden elegir para cada consulta.

Ejemplos:

Entrada: arr[ ] = {30, 31, 32, 33, 32, 32, 31, 30, 30, 32}, Q[ ] = {1, 3}
Salida: 4 9
Explicación: 
La frecuencia de 32 es 4, 30 es 3, 31 es 2 y 33 es 1.
Para Q[0](=1), elija todos los 32. Por lo tanto, cuente = 4.
Para Q[1](=3), elija todos los 32, 30 y 31. Por lo tanto cuenta = 4 + 3 + 2 = 9.

Entrada: arr[ ] = {22, 35, 22, 22, 35}, Q[ ] = {4, 5, 1}
Salida: 5 5 3

Enfoque: Este problema se puede resolver almacenando las frecuencias de cada elemento en un mapa . Siga los pasos a continuación para resolver este problema:

• Inicialice una estructura de datos de mapa , digamos Map e itere sobre la array arr[], luego almacene la frecuencia de cada elemento de la array arr[] en Map.
• Almacene todos los valores de Map en una array, digamos Cum_freq[], luego ordene la array Cum_freq[] en orden decreciente.
• Iterar en el rango [1, tamaño de Cum_freq[]] usando la variable i y actualizar el valor de Cum_freq[i] + Cum_freq[i-1] en Cum_freq[i].
• Iterar en el rango [0, tamaño de las consultas []] usando la variable i:
  • Si consultas[i] >= tamaño de Cum_freq[], imprima N.
  • De lo contrario, imprima Cum_freq[consultas[i] – 1].

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 the maximum number
// of elements can pick for each query
void findMaxEleCanPick(int arr[], int queries[], int n, int m)
{
    map<int,int>mp;
    for(int i = 0; i < n; i++)
    {
         if(mp.find(arr[i]) != mp.end())
         {
             mp[arr[i]] += 1;
         }
         else
         mp[arr[i]] = 1;
    }
    vector<int>Cum_freq;
   
    // taking out frequencies from map
    for(auto i:mp)
    Cum_freq.push_back(i.second);
   
    // Sorting in decreasing order
    sort(Cum_freq.begin(),Cum_freq.end(),greater<int>());
   
    // Taking cumulative sum
    for(int i = 1; i < Cum_freq.size(); i++)
    Cum_freq[i] += Cum_freq[i - 1];
   
    // Performing each query
    for(int k = 0; k < m; k++)
    {
         if(queries[k] >= m)
         cout << n << " ";
         else
         cout<<Cum_freq[queries[k] - 1];
    }
     
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[5] = {22, 35, 22, 22, 35};
    int queries[3] = { 4, 5, 1 };
   
    // Function Call
    findMaxEleCanPick(arr,queries,5,3);
    return 0;
}
 
// This code is contributed by dwivediyash

// Java program for the above approach
 
//Function to find the maximum number
//of elements can pick for each query
import java.io.*;
import java.util.*;
import java.util.HashMap;
class GFG {
static void findMaxEleCanPick(Integer arr[],Integer queries[],Integer n,Integer m)
{
HashMap<Integer, Integer> mp = new HashMap<>();
    for(int i=0;i<n;i++)
    {
         if(mp.containsKey(arr[i]))
         {
            mp.put(arr[i],mp.get(arr[i]+1));
         }
         else
         mp.put(arr[i],1);
    }
     int Cum_freq[] = new int[n];
    //taking out frequencies from map
    int x=0;
    for(Map.Entry<Integer, Integer> i : mp.entrySet())
    Cum_freq[x++]=i.getValue();
    //Sorting in decreasing order
    Arrays.sort(arr, Collections.reverseOrder());
    //Taking cumulative sum
    for(Integer i=1;i<n;i++)
    Cum_freq[i]+=Cum_freq[i-1];
    //Performing each query
    for(Integer k=0;k<m;k++)
    {
         if(queries[k]>=m)
         System.out.println(n+" ");
         else
         System.out.println(queries[k]-1);
    }
     
}
 
// Driver Code
     
     
     public static void main(String[] args)
    {
        //Given Input
        Integer arr[]={22, 35, 22, 22, 35};
        Integer queries[]={ 4, 5, 1 };
        // Function Call
        findMaxEleCanPick(arr,queries,5,3);
         
    }
}
// java code added by dwivediyash

# Python program for the above approach
 
# Function to find the maximum number
# of elements can pick for each query
def findMaxEleCanPick(arr, queries):
 
    # Total elements
    N = len(arr)
 
    # Using dictionary
    Map = dict()
 
    # Traversing the arr
    for ele in arr:
 
        # Updating the dictionary
        Map[ele] = 1 + Map.get(ele, 0)
 
    # Taking out frequencies from dictionary
    Cum_freq = list(Map.values())
 
    # Sorting in decreasing order
    Cum_freq.sort(reverse = True)
 
    # Taking cumulative sum
    for i in range(1, len(Cum_freq)):
        Cum_freq[i] += Cum_freq[i-1]
 
    # Performing each query
    for K in queries:
        if K >= len(Cum_freq):
            print(N, end = " ")
        else:
            print(Cum_freq[K-1], end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    # Given Input
    arr = [ 22, 35, 22, 22, 35 ]
    queries = [ 4, 5, 1 ]
 
    # Function Call
    findMaxEleCanPick(arr, queries)

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the maximum number
// of elements can pick for each query
static void findMaxEleCanPick(int []arr, int []queries, int n, int m)
{
    Dictionary<int,int> mp = new Dictionary<int,int>();
    for(int i = 0; i < n; i++)
    {
         if(mp.ContainsKey(arr[i]))
         {
             mp[arr[i]] += 1;
         }
         else
         mp.Add(arr[i],1);
    }
    List<int> Cum_freq = new List<int>();
   
    // taking out frequencies from map
    foreach(KeyValuePair<int,int> entry in mp)
    Cum_freq.Add(entry.Value);
   
    // Sorting in decreasing order
    Cum_freq.Sort();
    Cum_freq.Reverse();
   
    // Taking cumulative sum
    for(int i = 1; i < Cum_freq.Count; i++)
    Cum_freq[i] += Cum_freq[i - 1];
   
    // Performing each query
    for(int k = 0; k < m; k++)
    {
         if(queries[k] >= m)
         Console.Write(n + " ");
         else
         Console.Write(Cum_freq[queries[k] - 1]);
    }
     
}
 
// Driver Code
public static void Main()
{
   
    // Given Input
    int []arr = {22, 35, 22, 22, 35};
    int []queries = { 4, 5, 1 };
   
    // Function Call
    findMaxEleCanPick(arr,queries,5,3);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// Javascript program for the above approach
 
// Function to find the maximum number
// of elements can pick for each query
function findMaxEleCanPick(arr, queries)
{
     
    // Total elements
    let N = arr.length;
     
    // Using dictionary
    let map = new Map();
     
    // Traversing the arr
    for(let ele of arr)
    {
         
        // Updating the dictionary
        if (map.has(ele))
            map.set(ele, map.get(ele) + 1);
        else
            map.set(ele, 1)
    }
     
    // Taking out frequencies from dictionary
    let Cum_freq = [...map.values()];
     
    // Sorting in decreasing order
    Cum_freq.sort((a, b) => b - a);
     
    // Taking cumulative sum
    for(let i = 1; i < Cum_freq.length; i++)
    {
        Cum_freq[i] += Cum_freq[i - 1];
    }
     
    // Performing each query
    for(let K of queries)
    {
        if (K >= Cum_freq.length)
        {
            document.write(N + " ");
        }
        else
        {
            document.write(Cum_freq[K - 1]);
        }
    }
}
 
// Driver Code
 
// Given Input
arr = [ 22, 35, 22, 22, 35 ];
queries = [ 4, 5, 1 ];
 
// Function Call
findMaxEleCanPick(arr, queries);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

5 5 3 

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