Dada una array de tamaño n , la array contiene números en el rango de 0 a k-1 , donde k es un número entero positivo y k <= n. Encuentre el número máximo que se repite en esta array. Por ejemplo, sea k 10, la array dada sea arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, el número máximo que se repite sería sea 2. La complejidad de tiempo esperada es O(n) y el espacio extra permitido es O(1) . Se permiten modificaciones a la array.
El enfoque ingenuo es ejecutar dos bucles, el bucle exterior elige un elemento uno por uno y el bucle interior cuenta una cantidad de ocurrencias del elemento seleccionado. Finalmente, devuelva el elemento con un recuento máximo. La complejidad temporal de este enfoque es O(n^2) .
Un mejor enfoque es crear una array de conteo de tamaño k e inicializar todos los elementos de conteo[] como 0. Iterar a través de todos los elementos de la array de entrada, y para cada elemento arr[i] , incrementar conteo[arr[i]] . Finalmente, itere a través de count[] y devuelva el índice con el valor máximo. Este enfoque requiere tiempo O(n), pero requiere espacio O(k).
A continuación se presenta el enfoque de O(n) tiempo y O(1) espacio adicional .
Entendamos el enfoque con un ejemplo simple donde arr[] = {2, 3, 3, 5, 3, 4, 1, 7}, k = 8, n = 8 (número de elementos en arr[]).
- Iterar a través de la array de entrada arr[] , para cada elemento arr[i] , incrementar arr[arr[i]%k] por k ( arr[] se convierte en {2, 11, 11, 29, 11, 12, 1, 15 } )
- Encuentre el valor máximo en la array modificada (el valor máximo es 29). El índice del valor máximo es el elemento repetido máximo (el índice de 29 es 3).
- Si queremos recuperar la array original, podemos iterar a través de la array una vez más y hacer arr[i] = arr[i] % k donde i varía de 0 a n-1 .
¿Cómo funciona el algoritmo anterior? Dado que usamos arr[i]%k como índice y agregamos el valor k en el índice arr[i]%k , el índice que es igual al elemento repetido máximo tendrá el valor máximo al final. Tenga en cuenta que k se agrega el número máximo de veces en el índice igual al elemento repetido máximo y todos los elementos de la array son más pequeños que k.
A continuación se muestra la implementación en C++ del algoritmo anterior.
C++
// C++ program to find the maximum repeating number
#include<iostream>
using namespace std;
// Returns maximum repeating element in arr[0..n-1].
// The array elements are in range from 0 to k-1
int maxRepeating(int* arr, int n, int k)
{
// Iterate though input array, for every element
// arr[i], increment arr[arr[i]%k] by k
for (int i = 0; i< n; i++)
arr[arr[i]%k] += k;
// Find index of the maximum repeating element
int max = arr[0], result = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
result = i;
}
}
/* Uncomment this code to get the original array back
for (int i = 0; i< n; i++)
arr[i] = arr[i]%k; */
// Return index of the maximum element
return result;
}
// Driver program to test above function
int main()
{
int arr[] = {2, 3, 3, 5, 3, 4, 1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 8;
cout << "The maximum repeating number is " <<
maxRepeating(arr, n, k) << endl;
return 0;
}
Java
// Java program to find the maximum repeating number
import java.io.*;
class MaxRepeating {
// Returns maximum repeating element in arr[0..n-1].
// The array elements are in range from 0 to k-1
static int maxRepeating(int arr[], int n, int k)
{
// Iterate though input array, for every element
// arr[i], increment arr[arr[i]%k] by k
for (int i = 0; i< n; i++)
arr[(arr[i]%k)] += k;
// Find index of the maximum repeating element
int max = arr[0], result = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
result = i;
}
}
/* Uncomment this code to get the original array back
for (int i = 0; i< n; i++)
arr[i] = arr[i]%k; */
// Return index of the maximum element
return result;
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {2, 3, 3, 5, 3, 4, 1, 7};
int n = arr.length;
int k=8;
System.out.println("Maximum repeating element is: " +
maxRepeating(arr,n,k));
}
}
/* This code is contributed by Devesh Agrawal */
Python3
# Python program to find the maximum repeating number
# Returns maximum repeating element in arr[0..n-1].
# The array elements are in range from 0 to k-1
def maxRepeating(arr, n, k):
# Iterate though input array, for every element
# arr[i], increment arr[arr[i]%k] by k
for i in range(0, n):
arr[arr[i]%k] += k
# Find index of the maximum repeating element
max = arr[0]
result = 0
for i in range(1, n):
if arr[i] > max:
max = arr[i]
result = i
# Uncomment this code to get the original array back
#for i in range(0, n):
# arr[i] = arr[i]%k
# Return index of the maximum element
return result
# Driver program to test above function
arr = [2, 3, 3, 5, 3, 4, 1, 7]
n = len(arr)
k = 8
print("The maximum repeating number is",maxRepeating(arr, n, k))
# This code is contributed by
# Smitha Dinesh Semwal
C#
//C# program to find the maximum repeating
// number
using System;
class GFG {
// Returns maximum repeating element
// in arr[0..n-1].
// The array elements are in range
// from 0 to k-1
static int maxRepeating(int []arr,
int n, int k)
{
// Iterate though input array, for
// every element arr[i], increment
// arr[arr[i]%k] by k
for (int i = 0; i< n; i++)
arr[(arr[i]%k)] += k;
// Find index of the maximum
// repeating element
int max = arr[0], result = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
result = i;
}
}
// Return index of the
// maximum element
return result;
}
/*Driver function to check for
above function*/
public static void Main ()
{
int []arr = {2, 3, 3, 5, 3, 4, 1, 7};
int n = arr.Length;
int k=8;
Console.Write("Maximum repeating "
+ "element is: "
+ maxRepeating(arr,n,k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to find the
// maximum repeating number
// Returns maximum repeating
// element in arr[0..n-1].
// The array elements are
// in range from 0 to k-1
function maxRepeating($arr, $n, $k)
{
// Iterate though input array,
// for every element arr[i],
// increment arr[arr[i]%k] by k
for ($i = 0; $i< $n; $i++)
$arr[$arr[$i] % $k] += $k;
// Find index of the
// maximum repeating
// element
$max = $arr[0];
$result = 0;
for ($i = 1; $i < $n; $i++)
{
if ($arr[$i] > $max)
{
$max = $arr[$i];
$result = $i;
}
}
/* Uncomment this code to
get the original array back
for (int i = 0; i< n; i++)
arr[i] = arr[i] % k; */
// Return index of the
// maximum element
return $result;
}
// Driver Code
$arr = array(2, 3, 3, 5, 3, 4, 1, 7);
$n = sizeof($arr);
$k = 8;
echo "The maximum repeating number is ",
maxRepeating($arr, $n, $k);
// This Code is contributed by Ajit
?>
Javascript
<script>
// JavaScript program to find the maximum repeating number
// Returns maximum repeating element in arr[0..n-1].
// The array elements are in range from 0 to k-1
function maxRepeating(arr, n, k)
{
// Iterate though input array, for every element
// arr[i], increment arr[arr[i]%k] by k
for (let i = 0; i< n; i++)
arr[arr[i]%k] += k;
// Find index of the maximum repeating element
let max = arr[0], result = 0;
for (let i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
result = i;
}
}
/* Uncomment this code to get the original array back
for (int i = 0; i< n; i++)
arr[i] = arr[i]%k; */
// Return index of the maximum element
return result;
}
// Driver program to test above function
let arr = [2, 3, 3, 5, 3, 4, 1, 7];
let n = arr.length;
let k = 8;
document.write("The maximum repeating number is " +
maxRepeating(arr, n, k) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
The maximum repeating number is 3
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Ejercicio: La solución anterior imprime solo un elemento repetido y no funciona si queremos imprimir todos los elementos repetidos máximos. Por ejemplo, si la array de entrada es {2, 3, 2, 3}, la solución anterior imprimirá solo 3. ¿Qué pasa si necesitamos imprimir tanto 2 como 3, ya que ambos ocurren la mayor cantidad de veces? Escriba una función O(n) de tiempo y O(1) de espacio adicional que imprima todos los elementos repetidos máximos. (Sugerencia: podemos usar el cociente máximo arr[i]/n en lugar del valor máximo en el paso 2).
Tenga en cuenta que las soluciones anteriores pueden causar un desbordamiento si agregar k repetidamente hace que el valor sea mayor que INT_MAX.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA