Dada una array de enteros que contienen elementos duplicados. La tarea es encontrar la suma de todos los elementos que aparecen más altos en la array dada. Esa es la suma de todos esos elementos cuya frecuencia es máxima en la array.
Ejemplos :
Input : arr[] = {1, 1, 2, 2, 2, 2, 3, 3, 3, 3}
Output : 20
The highest occurring elements are 3 and 2 and their
frequency is 4. Therefore sum of all 3's and 2's in the
array = 3+3+3+3+2+2+2+2 = 20.
Input : arr[] = {10, 20, 30, 40, 40}
Output : 80
Enfoque :
- Recorra la array y use un mapa_desordenado en C++ para almacenar la frecuencia de los elementos de la array de modo que la clave del mapa sea el elemento de la array y el valor sea su frecuencia en la array.
- Luego, recorra el mapa para encontrar la frecuencia del elemento máximo que ocurre.
- Ahora, para encontrar la suma, recorra el mapa nuevamente y para todos los elementos con la frecuencia máxima, busque la frecuencia_del_elemento_máximo_de_ocurrencia*elemento_máximo_de_ocurrencia y encuentre su suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the sum of all maximum
// occurring elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of all maximum
// occurring elements in an array
int findSum(int arr[], int N)
{
// Store frequencies of elements
// of the array
unordered_map<int, int> mp;
for (int i = 0; i < N; i++)
mp[arr[i]]++;
// Find the max frequency
int maxFreq = 0;
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
if (itr->second > maxFreq) {
maxFreq = itr->second;
}
}
// Traverse the map again and find the sum
int sum = 0;
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
if (itr->second == maxFreq) {
sum += itr->first * itr->second;
}
}
return sum;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, N);
return 0;
}
Java
// Java program to find the sum of all maximum
// occurring elements in an array
import java.util.*;
class GFG
{
// Function to find the sum of all maximum
// occurring elements in an array
static int findSum(int arr[], int N)
{
// Store frequencies of elements
// of the array
Map<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);
}
}
// Find the max frequency
int maxFreq = 0;
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
{
if (entry.getValue() > maxFreq)
{
maxFreq = entry.getValue();
}
}
// Traverse the map again and find the sum
int sum = 0;
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
{
if (entry.getValue() == maxFreq)
{
sum += entry.getKey() * entry.getValue();
}
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 };
int N = arr.length;
System.out.println(findSum(arr, N));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find the Sum of all maximum # occurring elements in an array # Function to find the Sum of all maximum # occurring elements in an array def findSum(arr, N): # Store frequencies of elements # of the array mp = dict() for i in range(N): mp[arr[i]] = mp.get(arr[i], 0) + 1 # Find the max frequency maxFreq = 0 for itr in mp: if (mp[itr] > maxFreq): maxFreq = mp[itr] # Traverse the map again and find the Sum Sum = 0 for itr in mp: if (mp[itr] == maxFreq): Sum += itr* mp[itr] return Sum # Driver Code arr= [1, 1, 2, 2, 2, 2, 3, 3, 3, 3 ] N = len(arr) print(findSum(arr, N)) # This code is contributed by mohit kumar
C#
// C# program to find the sum of all maximum
// occurring elements in an array
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the sum of all maximum
// occurring elements in an array
static int findSum(int []arr, int N)
{
// Store frequencies of elements
// of the array
Dictionary<int,int> mp = new Dictionary<int,int>();
for (int i = 0 ; i < N; i++)
{
if(mp.ContainsKey(arr[i]))
{
var val = mp[arr[i]];
mp.Remove(arr[i]);
mp.Add(arr[i], val + 1);
}
else
{
mp.Add(arr[i], 1);
}
}
// Find the max frequency
int maxFreq = 0;
foreach(KeyValuePair<int, int> entry in mp)
{
if (entry.Value > maxFreq)
{
maxFreq = entry.Value;
}
}
// Traverse the map again and find the sum
int sum = 0;
foreach(KeyValuePair<int, int> entry in mp)
{
if (entry.Value == maxFreq)
{
sum += entry.Key * entry.Value;
}
}
return sum;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 };
int N = arr.Length;
Console.WriteLine(findSum(arr, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find
// the sum of all maximum
// occurring elements in an array
// Function to find the sum of all maximum
// occurring elements in an array
function findSum(arr,N)
{
// Store frequencies of elements
// of the array
let mp = new Map();
for (let i = 0 ; i < N; i++)
{
if(mp.has(arr[i]))
{
mp.set(arr[i], mp.get(arr[i])+1);
}
else
{
mp.set(arr[i], 1);
}
}
// Find the max frequency
let maxFreq = 0;
for (let [key, value] of mp.entries())
{
if (value > maxFreq)
{
maxFreq = value;
}
}
// Traverse the map again and find the sum
let sum = 0;
for (let [key, value] of mp.entries())
{
if (value == maxFreq)
{
sum += key * value;
}
}
return sum;
}
// Driver Code
let arr=[ 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 ];
let N = arr.length;
document.write(findSum(arr, N));
// This code is contributed by patel2127
</script>
Producción:
20
Complejidad de tiempo : O(N), donde N es el número de elementos en la array.