Dadas dos arrays desordenadas arr1[] y arr2[] , la tarea es encontrar la suma de elementos de arr1[] tal que el número de elementos menores o iguales que ellos en arr2[] sea el máximo.
Ejemplos:
Entrada: arr1[] = {1, 2, 3, 4, 7, 9}, arr2[] = {0, 1, 2, 1, 1, 4}
Salida: 20 La siguiente
tabla muestra el recuento de elementos en arr2[ ] que son ≤ los elementos de arr1[]
arr1[yo] Contar 1 4 2 5 3 5 4 6 7 6 9 6 La cuenta de 4, 7 y 9 es máxima.
Por lo tanto, la suma resultante es 4 + 7 + 9 = 20.
Entrada: arr1[] = {5, 10, 2, 6, 1, 8, 6, 12}, arr2[] = {6, 5, 11, 4 , 2, 3, 7}
Salida: 12
Enfoque: la idea detrás de una solución eficiente para el problema anterior es usar el hash de la segunda array y luego encontrar la suma acumulativa de una array hash. Después de eso, el recuento de elementos en la segunda array menor o igual a los elementos de la primera array se puede calcular fácilmente. Esto dará una array de frecuencia que representa el recuento de elementos en la segunda array menor o igual a los elementos de la primera array desde donde se puede calcular la suma de los elementos de la primera array correspondiente a la frecuencia máxima en la array de frecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
#define MAX 100000
// Function to return the required sum
int findSumofEle(int arr1[], int m,
int arr2[], int n)
{
// Creating hash array initially
// filled with zero
int hash[MAX] = { 0 };
// Calculate the frequency
// of elements of arr2[]
for (int i = 0; i < n; i++)
hash[arr2[i]]++;
// Running sum of hash array
// such that hash[i] will give count of
// elements less than or equal to i in arr2[]
for (int i = 1; i < MAX; i++)
hash[i] = hash[i] + hash[i - 1];
// To store the maximum value of
// the number of elements in arr2[] which are
// smaller than or equal to some element of arr1[]
int maximumFreq = 0;
for (int i = 0; i < m; i++)
maximumFreq = max(maximumFreq, hash[arr1[i]]);
// Calculate the sum of elements from arr1[]
// corresponding to maximum frequency
int sumOfElements = 0;
for (int i = 0; i < m; i++)
sumOfElements += (maximumFreq == hash[arr1[i]]) ? arr1[i] : 0;
// Return the required sum
return sumOfElements;
}
// Driver code
int main()
{
int arr1[] = { 2, 5, 6, 8 };
int arr2[] = { 4, 10 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
cout << findSumofEle(arr1, m, arr2, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 100000;
// Function to return the required sum
static int findSumofEle(int arr1[], int m,
int arr2[], int n)
{
// Creating hash array initially
// filled with zero
int hash[] = new int[MAX];
// Calculate the frequency
// of elements of arr2[]
for (int i = 0; i < n; i++)
{
hash[arr2[i]]++;
}
// Running sum of hash array
// such that hash[i] will give count of
// elements less than or equal to i in arr2[]
for (int i = 1; i < MAX; i++)
{
hash[i] = hash[i] + hash[i - 1];
}
// To store the maximum value of
// the number of elements in arr2[] which are
// smaller than or equal to some element of arr1[]
int maximumFreq = 0;
for (int i = 0; i < m; i++)
{
maximumFreq = Math.max(maximumFreq, hash[arr1[i]]);
}
// Calculate the sum of elements from arr1[]
// corresponding to maximum frequency
int sumOfElements = 0;
for (int i = 0; i < m; i++)
{
sumOfElements += (maximumFreq == hash[arr1[i]]) ? arr1[i] : 0;
}
// Return the required sum
return sumOfElements;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = {2, 5, 6, 8};
int arr2[] = {4, 10};
int m = arr1.length;
int n = arr2.length;
System.out.println(findSumofEle(arr1, m, arr2, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach MAX = 100000 # Function to return the required sum def findSumofEle(arr1, m, arr2, n): # Creating hash array initially # filled with zero hash = [0 for i in range(MAX)] # Calculate the frequency # of elements of arr2[] for i in range(n): hash[arr2[i]] += 1 # Running sum of hash array # such that hash[i] will give count of # elements less than or equal to i in arr2[] for i in range(1, MAX, 1): hash[i] = hash[i] + hash[i - 1] # To store the maximum value of # the number of elements in arr2[] # which are smaller than or equal # to some element of arr1[] maximumFreq = 0 for i in range(m): maximumFreq = max(maximumFreq, hash[arr1[i]]) # Calculate the sum of elements from arr1[] # corresponding to maximum frequency sumOfElements = 0 for i in range(m): if (maximumFreq == hash[arr1[i]]): sumOfElements += arr1[i] # Return the required sum return sumOfElements # Driver code if __name__ == '__main__': arr1 = [2, 5, 6, 8] arr2 = [4, 10] m = len(arr1) n = len(arr2) print(findSumofEle(arr1, m, arr2, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100000;
// Function to return the required sum
static int findSumofEle(int[] arr1, int m,
int[] arr2, int n)
{
// Creating hash array initially
// filled with zero
int[] hash = new int[MAX];
// Calculate the frequency
// of elements of arr2[]
for (int i = 0; i < n; i++)
{
hash[arr2[i]]++;
}
// Running sum of hash array
// such that hash[i] will give count of
// elements less than or equal to i in arr2[]
for (int i = 1; i < MAX; i++)
{
hash[i] = hash[i] + hash[i - 1];
}
// To store the maximum value of
// the number of elements in arr2[] which are
// smaller than or equal to some element of arr1[]
int maximumFreq = 0;
for (int i = 0; i < m; i++)
{
maximumFreq = Math.Max(maximumFreq, hash[arr1[i]]);
}
// Calculate the sum of elements from arr1[]
// corresponding to maximum frequency
int sumOfElements = 0;
for (int i = 0; i < m; i++)
{
sumOfElements += (maximumFreq == hash[arr1[i]]) ? arr1[i] : 0;
}
// Return the required sum
return sumOfElements;
}
// Driver code
public static void Main()
{
int[] arr1 = {2, 5, 6, 8};
int[] arr2 = {4, 10};
int m = arr1.Length;
int n = arr2.Length;
Console.WriteLine(findSumofEle(arr1, m, arr2, n));
}
}
// This code has been contributed by Code_Mech.
PHP
<?php
// PHP implementation of the approach
$MAX = 10000;
// Function to return the required sum
function findSumofEle($arr1, $m, $arr2, $n)
{
// Creating hash array initially
// filled with zero
$hash = array_fill(0, $GLOBALS['MAX'], 0);
// Calculate the frequency
// of elements of arr2[]
for ($i = 0; $i < $n; $i++)
$hash[$arr2[$i]]++;
// Running sum of hash array
// such that hash[i] will give count of
// elements less than or equal to i in arr2[]
for ($i = 1; $i < $GLOBALS['MAX']; $i++)
$hash[$i] = $hash[$i] + $hash[$i - 1];
// To store the maximum value of
// the number of elements in arr2[] which are
// smaller than or equal to some element of arr1[]
$maximumFreq = 0;
for ($i = 0; $i < $m; $i++)
$maximumFreq = max($maximumFreq,
$hash[$arr1[$i]]);
// Calculate the sum of elements from arr1[]
// corresponding to maximum frequency
$sumOfElements = 0;
for ($i = 0; $i < $m; $i++)
$sumOfElements += ($maximumFreq == $hash[$arr1[$i]]) ?
$arr1[$i] : 0;
// Return the required sum
return $sumOfElements;
}
// Driver code
$arr1 = array( 2, 5, 6, 8 );
$arr2 = array( 4, 10 );
$m = count($arr1);
$n = count($arr2);
echo findSumofEle($arr1, $m, $arr2, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the required sum
function findSumofEle(arr1, m, arr2, n)
{
let MAX = 100000;
// Creating hash array initially
// filled with zero
let hash = new Array(MAX);
for(let i = 0; i < MAX; i++)
hash[i] = 0;
// Calculate the frequency
// of elements of arr2[]
for(let i = 0; i < n; i++)
hash[arr2[i]]++;
// Running sum of hash array such
// that hash[i] will give count of
// elements less than or equal
// to i in arr2[]
for(let i = 1; i < MAX; i++)
hash[i] = hash[i] + hash[i - 1];
// To store the maximum value of
// the number of elements in
// arr2[] which are smaller
// than or equal to some
// element of arr1[]
let maximumFreq = 0;
for(let i = 0; i < m; i++)
{
maximumFreq = Math.max(maximumFreq,
hash[arr1[i]]);
}
// Calculate the sum of elements from arr1[]
// corresponding to maximum frequency
let sumOfElements = 0;
for(let i = 0; i < m; i++)
{
if (maximumFreq == hash[arr1[i]])
sumOfElements += arr1[i];
}
// Return the required sum
return sumOfElements;
}
// Driver code
let arr1 = [ 2, 5, 6, 8 ];
let arr2 = [ 4, 10 ];
let m = arr1.length;
let n = arr2.length;
document.write(findSumofEle(arr1, m, arr2, n));
// This code is contributed by mohit kumar 29
</script>
19
Complejidad de Tiempo: O(MAX)
Espacio Auxiliar: O(MAX), ya que se ha tomado MAX espacio extra.
Otro enfoque eficiente: uso de la biblioteca de plantillas estándar (STL)
En este enfoque, primero ordenaremos la segunda array. Luego, iteramos en la primera array y para cada elemento de la primera array, encontraremos el recuento de elementos más pequeños en arr2 usando STL de límite inferior en tiempo O (log (n)) . Si el recuento de dichos elementos es máximo, podemos decir que el elemento correspondiente en arr1 estará en la respuesta. De esta manera, seguimos iterando en la primera array e intentamos encontrar los elementos con el recuento máximo en la segunda array y agregaremos esos elementos a la respuesta. La complejidad temporal de este enfoque es O(n*log(n)+m*log(n))y por lo tanto es mejor que el enfoque anterior para valores pequeños de n y m. Además, el espacio auxiliar en este enfoque es O(1) , que es mejor que el enfoque anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the required sum
int findSumofEle(int arr1[], int m, int arr2[], int n)
{
// Variable to store the
// maximum count of numbers
// which are smaller than
// any element
int maxi=INT_MIN;
// Variable to store the answer
int ans=0;
sort(arr2,arr2+n);
for(int i=0;i<m;i++)
{
// find the index of first element
// in arr2 which is greater than
// current element in arr1
int y = lower_bound(arr2,arr2+n,arr1[i]+1)-arr2;
// subtracting 1 to get the count of all smaller
// elements
y=y-1;
// if the count of all such element
// is highest for this element in arr1
// then it will be the answer
if(y>maxi)
{
maxi=y;
ans=arr1[i];
}
// if count of all such element is
// equal to highest for this element
// in arr1 then add this element also in answer
else if(y==maxi)
{
ans+=arr1[i];
}
}
// Return the answer
return ans;
}
// Driver code
int main()
{
int arr1[] = {5, 10, 2, 6, 1, 8, 6, 12};
int arr2[] = { 6, 5, 11, 4, 2, 3, 7};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
cout << findSumofEle(arr1, m, arr2, n);
return 0;
}
// This code is contributed by Pushpesh Raj
19
Complejidad de tiempo: O(n*log(n)+m*log(n)) donde m y n son el tamaño de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA