Dada una array desordenada de n enteros que pueden contener números enteros del 1 al n. Algunos elementos se pueden repetir varias veces y otros elementos pueden estar ausentes de la array. Cuente la frecuencia de todos los elementos que están presentes e imprima los elementos que faltan.
Ejemplos:
Input: arr[] = {2, 3, 3, 2, 5}
Output: Below are frequencies of all elements
1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1
Explanation: Frequency of elements 1 is
0, 2 is 2, 3 is 2, 4 is 0 and 5 is 1.
Input: arr[] = {4, 4, 4, 4}
Output: Below are frequencies of all elements
1 -> 0
2 -> 0
3 -> 0
4 -> 4
Explanation: Frequency of elements 1 is
0, 2 is 0, 3 is 0 and 4 is 4.
Solución simple
- Enfoque: Cree un espacio adicional de tamaño n, ya que los elementos de la array están en el rango de 1 a n. Use el espacio adicional como HashMap . Recorra la array y actualice el recuento del elemento actual. Finalmente, imprima las frecuencias del HashMap junto con los índices.
- Algoritmo:
- Cree un espacio adicional de tamaño n ( hm ), utilícelo como HashMap.
- Atraviesa la array de principio a fin.
- Para cada elemento, actualice hm[array[i]-1] , es decir, hm[array[i]-1]++
- Ejecute un bucle de 0 a n e imprima hm[array[i]-1] junto con el índice i
Implementación:
C++
// C++ program to print frequencies of all array
// elements in O(n) extra space and O(n) time
#include<bits/stdc++.h>
using namespace std;
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
void findCounts(int *arr, int n)
{
//Hashmap
int hash[n]={0};
// Traverse all array elements
int i = 0;
while (i<n)
{
//update the frequency of array[i]
hash[arr[i]-1]++;
//increase the index
i++;
}
printf("\nBelow are counts of all elements\n");
for (int i=0; i<n; i++)
printf("%d -> %d\n", i+1, hash[i]);
}
// Driver program to test above function
int main()
{
int arr[] = {2, 3, 3, 2, 5};
findCounts(arr, sizeof(arr)/ sizeof(arr[0]));
int arr1[] = {1};
findCounts(arr1, sizeof(arr1)/ sizeof(arr1[0]));
int arr3[] = {4, 4, 4, 4};
findCounts(arr3, sizeof(arr3)/ sizeof(arr3[0]));
int arr2[] = {1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1};
findCounts(arr2, sizeof(arr2)/ sizeof(arr2[0]));
int arr4[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
findCounts(arr4, sizeof(arr4)/ sizeof(arr4[0]));
int arr5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
findCounts(arr5, sizeof(arr5)/ sizeof(arr5[0]));
int arr6[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
findCounts(arr6, sizeof(arr6)/ sizeof(arr6[0]));
return 0;
}
Java
// Java program to print frequencies of all array
// elements in O(n) extra space and O(n) time
import java.util.*;
class GFG{
// Function to find counts of all elements
// present in arr[0..n-1]. The array elements
// must be range from 1 to n
public static void findCounts(int arr[], int n)
{
// Hashmap
int hash[] = new int[n];
Arrays.fill(hash, 0);
// Traverse all array elements
int i = 0;
while (i < n)
{
// Update the frequency of array[i]
hash[arr[i] - 1]++;
// Increase the index
i++;
}
System.out.println("\nBelow are counts " +
"of all elements");
for(i = 0; i < n; i++)
{
System.out.println((i + 1) + " -> " +
hash[i]);
}
}
// Driver code
public static void main(String []args)
{
int arr[] = { 2, 3, 3, 2, 5 };
findCounts(arr, arr.length);
int arr1[] = {1};
findCounts(arr1, arr1.length);
int arr3[] = { 4, 4, 4, 4 };
findCounts(arr3, arr3.length);
int arr2[] = { 1, 3, 5, 7, 9,
1, 3, 5, 7, 9, 1 };
findCounts(arr2, arr2.length);
int arr4[] = { 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3 };
findCounts(arr4, arr4.length);
int arr5[] = { 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11 };
findCounts(arr5, arr5.length);
int arr6[] = { 11, 10, 9, 8, 7,
6, 5, 4, 3, 2, 1 };
findCounts(arr6, arr6.length);
}
}
// This code is contributed by rag2127
Python3
# Python3 program to print frequencies
# of all array elements in O(n) extra
# space and O(n) time
# Function to find counts of all
# elements present in arr[0..n-1].
# The array elements must be range
# from 1 to n
def findCounts(arr, n):
# Hashmap
hash = [0 for i in range(n)]
# Traverse all array elements
i = 0
while (i < n):
# Update the frequency of array[i]
hash[arr[i] - 1] += 1
# Increase the index
i += 1
print("Below are counts of all elements")
for i in range(n):
print(i + 1, "->", hash[i], end = " ")
print()
# Driver code
arr = [ 2, 3, 3, 2, 5 ]
findCounts(arr, len(arr))
arr1 = [1]
findCounts(arr1, len(arr1))
arr3 = [ 4, 4, 4, 4 ]
findCounts(arr3, len(arr3))
arr2 = [ 1, 3, 5, 7, 9,
1, 3, 5, 7, 9, 1 ]
findCounts(arr2, len(arr2))
arr4 = [ 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3 ]
findCounts(arr4, len(arr4))
arr5 = [ 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11 ]
findCounts(arr5, len(arr5))
arr6 = [ 11, 10, 9, 8, 7,
6, 5, 4, 3, 2, 1 ]
findCounts(arr6, len(arr6))
# This code is contributed by avanitrachhadiya2155
C#
// C# program to print frequencies of all array
// elements in O(n) extra space and O(n) time
using System;
class GFG
{
// Function to find counts of all elements
// present in arr[0..n-1]. The array elements
// must be range from 1 to n
public static void findCounts(int[] arr, int n)
{
// Hashmap
int[] hash = new int[n];
// Traverse all array elements
int i = 0;
while (i < n)
{
// Update the frequency of array[i]
hash[arr[i] - 1]++;
// Increase the index
i++;
}
Console.WriteLine("\nBelow are counts "
+ "of all elements");
for (i = 0; i < n; i++)
{
Console.WriteLine((i + 1) + " -> " + hash[i]);
}
}
// Driver code
static public void Main()
{
int[] arr = new int[] { 2, 3, 3, 2, 5 };
findCounts(arr, arr.Length);
int[] arr1 = new int[] { 1 };
findCounts(arr1, arr1.Length);
int[] arr3 = new int[] { 4, 4, 4, 4 };
findCounts(arr3, arr3.Length);
int[] arr2
= new int[] { 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1 };
findCounts(arr2, arr2.Length);
int[] arr4
= new int[] { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 };
findCounts(arr4, arr4.Length);
int[] arr5 = new int[] { 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11 };
findCounts(arr5, arr5.Length);
int[] arr6 = new int[] { 11, 10, 9, 8, 7, 6,
5, 4, 3, 2, 1 };
findCounts(arr6, arr6.Length);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program to print frequencies of all array
// elements in O(n) extra space and O(n) time
// Function to find counts of all elements
// present in arr[0..n-1]. The array elements
// must be range from 1 to n
function findCounts(arr,n)
{
// Hashmap
let hash = new Array(n);
for(let i=0;i<n;i++)
{
hash[i]=0;
}
// Traverse all array elements
let i = 0;
while (i < n)
{
// Update the frequency of array[i]
hash[arr[i] - 1]++;
// Increase the index
i++;
}
document.write("<br>Below are counts " +
"of all elements<br>");
for(i = 0; i < n; i++)
{
document.write((i + 1) + " -> " +
hash[i]+"<br>");
}
}
// Driver code
let arr = [ 2, 3, 3, 2, 5 ];
findCounts(arr, arr.length);
let arr1 = [1];
findCounts(arr1, arr1.length);
let arr3 = [ 4, 4, 4, 4 ];
findCounts(arr3, arr3.length);
let arr2 = [ 1, 3, 5, 7, 9,
1, 3, 5, 7, 9, 1 ];
findCounts(arr2, arr2.length);
let arr4 = [ 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3 ];
findCounts(arr4, arr4.length);
let arr5 = [ 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11 ];
findCounts(arr5, arr5.length);
let arr6 = [ 11, 10, 9, 8, 7,
6, 5, 4, 3, 2, 1 ];
findCounts(arr6, arr6.length);
// This code is contributed by ab2127
</script>
Producción
Below are counts of all elements 1 -> 0 2 -> 2 3 -> 2 4 -> 0 5 -> 1 Below are counts of all elements 1 -> 1 Below are counts of all elements 1 -> 0 2 -> 0 3 -> 0 4 -> 4 Below are counts of all elements 1 -> 3 2 -> 0 3 -> 2 4 -> 0 5 -> 2 6 -> 0 7 -> 2 8 -> 0 9 -> 2 10 -> 0 11 -> 0 Below are counts of all elements 1 -> 0 2 -> 0 3 -> 11 4 -> 0 5 -> 0 6 -> 0 7 -> 0 8 -> 0 9 -> 0 10 -> 0 11 -> 0 Below are counts of all elements 1 -> 1 2 -> 1 3 -> 1 4 -> 1 5 -> 1 6 -> 1 7 -> 1 8 -> 1 9 -> 1 10 -> 1 11 -> 1 Below are counts of all elements 1 -> 1 2 -> 1 3 -> 1 4 -> 1 5 -> 1 6 -> 1 7 -> 1 8 -> 1 9 -> 1 10 -> 1 11 -> 1
- Análisis de Complejidad:
- Complejidad temporal: O(n).
Como un solo recorrido de la array toma O (n) tiempo. - Complejidad espacial: O(n).
Para almacenar todos los elementos en un espacio HashMap O(n) es necesario.
- Complejidad temporal: O(n).
A continuación se muestran dos métodos eficientes para resolver esto en tiempo O(n) y espacio extra O(1). Ambos métodos modifican la array dada para lograr O(1) espacio adicional.
Método 2 : haciendo que los elementos sean negativos.
- Enfoque: la idea es recorrer la array dada, usar elementos como índice y almacenar sus recuentos en el índice. Considere el enfoque básico, se necesita un Hashmap de tamaño n y la array también es de tamaño n. Entonces, la array se puede usar como un hashmap, todos los elementos de la array son del 1 al n, es decir, todos son elementos positivos. Entonces la frecuencia se puede almacenar como negativa. Esto podría conducir a un problema. Deje que el i-ésimo elemento sea un, entonces el conteo debe almacenarse en la array [a-1], pero cuando se almacene la frecuencia, el elemento se perderá. Para solucionar este problema, primero, reemplace el i-ésimo elemento por array[a-1] y luego coloque -1 en array[a-1]. Entonces, nuestra idea es reemplazar el elemento por frecuencia y almacenar el elemento en el índice actual y si el elemento en array[a-1] ya es negativo, entonces ya está reemplazado por una frecuencia, así que disminuya array[a-1] .
- Algoritmo:
- Atraviesa la array de principio a fin.
- Para cada elemento, compruebe si el elemento es menor o igual a cero o no. Si es negativo o cero, omita el elemento ya que es frecuencia.
- Si un elemento ( e = array[i] – 1 ) es positivo, compruebe si array[e] es positivo o no. Si es positivo, eso significa que es la primera aparición de e en la array y reemplaza array[i] con array[e] , es decir, array[i] = array[e] y asigna array[e] = -1 . Si array[e] es negativo, entonces no es la primera aparición, actualizar array[e] como array[e]– y actualizar array[i] como array[i] = 0 .
- Nuevamente, recorra la array e imprima i+1 como valor y array[i] como frecuencia.
- Implementación:
C++
// C++ program to print frequencies of all array
// elements in O(1) extra space and O(n) time
#include<bits/stdc++.h>
using namespace std;
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
void findCounts(int *arr, int n)
{
// Traverse all array elements
int i = 0;
while (i<n)
{
// If this element is already processed,
// then nothing to do
if (arr[i] <= 0)
{
i++;
continue;
}
// Find index corresponding to this element
// For example, index for 5 is 4
int elementIndex = arr[i]-1;
// If the elementIndex has an element that is not
// processed yet, then first store that element
// to arr[i] so that we don't lose anything.
if (arr[elementIndex] > 0)
{
arr[i] = arr[elementIndex];
// After storing arr[elementIndex], change it
// to store initial count of 'arr[i]'
arr[elementIndex] = -1;
}
else
{
// If this is NOT first occurrence of arr[i],
// then decrement its count.
arr[elementIndex]--;
// And initialize arr[i] as 0 means the element
// 'i+1' is not seen so far
arr[i] = 0;
i++;
}
}
printf("\nBelow are counts of all elements\n");
for (int i=0; i<n; i++)
printf("%d -> %d\n", i+1, abs(arr[i]));
}
// Driver program to test above function
int main()
{
int arr[] = {2, 3, 3, 2, 5};
findCounts(arr, sizeof(arr)/ sizeof(arr[0]));
int arr1[] = {1};
findCounts(arr1, sizeof(arr1)/ sizeof(arr1[0]));
int arr3[] = {4, 4, 4, 4};
findCounts(arr3, sizeof(arr3)/ sizeof(arr3[0]));
int arr2[] = {1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1};
findCounts(arr2, sizeof(arr2)/ sizeof(arr2[0]));
int arr4[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
findCounts(arr4, sizeof(arr4)/ sizeof(arr4[0]));
int arr5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
findCounts(arr5, sizeof(arr5)/ sizeof(arr5[0]));
int arr6[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
findCounts(arr6, sizeof(arr6)/ sizeof(arr6[0]));
return 0;
}
Java
// Java program to print frequencies of all array
// elements in O(1) extra space and O(n) time
class CountFrequencies
{
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
void findCounts(int arr[], int n)
{
// Traverse all array elements
int i = 0;
while (i < n)
{
// If this element is already processed,
// then nothing to do
if (arr[i] <= 0)
{
i++;
continue;
}
// Find index corresponding to this element
// For example, index for 5 is 4
int elementIndex = arr[i] - 1;
// If the elementIndex has an element that is not
// processed yet, then first store that element
// to arr[i] so that we don't lose anything.
if (arr[elementIndex] > 0)
{
arr[i] = arr[elementIndex];
// After storing arr[elementIndex], change it
// to store initial count of 'arr[i]'
arr[elementIndex] = -1;
}
else
{
// If this is NOT first occurrence of arr[i],
// then decrement its count.
arr[elementIndex]--;
// And initialize arr[i] as 0 means the element
// 'i+1' is not seen so far
arr[i] = 0;
i++;
}
}
System.out.println("Below are counts of all elements");
for (int j = 0; j < n; j++)
System.out.println(j+1 + "->" + Math.abs(arr[j]));
}
// Driver program to test above functions
public static void main(String[] args)
{
CountFrequencies count = new CountFrequencies();
int arr[] = {2, 3, 3, 2, 5};
count.findCounts(arr, arr.length);
int arr1[] = {1};
count.findCounts(arr1, arr1.length);
int arr3[] = {4, 4, 4, 4};
count.findCounts(arr3, arr3.length);
int arr2[] = {1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1};
count.findCounts(arr2, arr2.length);
int arr4[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
count.findCounts(arr4, arr4.length);
int arr5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
count.findCounts(arr5, arr5.length);
int arr6[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
count.findCounts(arr6, arr6.length);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
# Python3 program to print frequencies of all array
# elements in O(1) extra space and O(n) time
# Function to find counts of all elements present in
# arr[0..n-1]. The array elements must be range from
# 1 to n
def findCounts(arr, n):
# Traverse all array elements
i = 0
while i<n:
# If this element is already processed,
# then nothing to do
if arr[i] <= 0:
i += 1
continue
# Find index corresponding to this element
# For example, index for 5 is 4
elementIndex = arr[i] - 1
# If the elementIndex has an element that is not
# processed yet, then first store that element
# to arr[i] so that we don't lose anything.
if arr[elementIndex] > 0:
arr[i] = arr[elementIndex]
# After storing arr[elementIndex], change it
# to store initial count of 'arr[i]'
arr[elementIndex] = -1
else:
# If this is NOT first occurrence of arr[i],
# then decrement its count.
arr[elementIndex] -= 1
# And initialize arr[i] as 0 means the element
# 'i+1' is not seen so far
arr[i] = 0
i += 1
print ("Below are counts of all elements")
for i in range(0,n):
print ("%d -> %d"%(i+1, abs(arr[i])))
print ("")
# Driver program to test above function
arr = [2, 3, 3, 2, 5]
findCounts(arr, len(arr))
arr1 = [1]
findCounts(arr1, len(arr1))
arr3 = [4, 4, 4, 4]
findCounts(arr3, len(arr3))
arr2 = [1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1]
findCounts(arr2, len(arr2))
arr4 = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
findCounts(arr4, len(arr4))
arr5 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
findCounts(arr5, len(arr5))
arr6 = [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
findCounts(arr6, len(arr6))
# This code is contributed
# by shreyanshi_19
C#
// C# program to print frequencies of
// all array elements in O(1) extra
// space and O(n) time
using System;
class GFG
{
// Function to find counts of all
// elements present in arr[0..n-1].
// The array elements must be range
// from 1 to n
void findCounts(int[] arr, int n)
{
// Traverse all array elements
int i = 0;
while (i < n)
{
// If this element is already
// processed, then nothing to do
if (arr[i] <= 0)
{
i++;
continue;
}
// Find index corresponding to
// this element. For example,
// index for 5 is 4
int elementIndex = arr[i] - 1;
// If the elementIndex has an element
// that is not processed yet, then
// first store that element to arr[i]
// so that we don't loose anything.
if (arr[elementIndex] > 0)
{
arr[i] = arr[elementIndex];
// After storing arr[elementIndex],
// change it to store initial count
// of 'arr[i]'
arr[elementIndex] = -1;
}
else
{
// If this is NOT first occurrence
// of arr[i], then decrement its count.
arr[elementIndex]--;
// And initialize arr[i] as 0 means
// the element 'i+1' is not seen so far
arr[i] = 0;
i++;
}
}
Console.Write("\nBelow are counts of " +
"all elements" + "\n");
for (int j = 0; j < n; j++)
Console.Write(j + 1 + "->" +
Math.Abs(arr[j]) + "\n");
}
// Driver Code
public static void Main()
{
GFG count = new GFG();
int[] arr = {2, 3, 3, 2, 5};
count.findCounts(arr, arr.Length);
int[] arr1 = {1};
count.findCounts(arr1, arr1.Length);
int[] arr3 = {4, 4, 4, 4};
count.findCounts(arr3, arr3.Length);
int[] arr2 = {1, 3, 5, 7, 9, 1,
3, 5, 7, 9, 1};
count.findCounts(arr2, arr2.Length);
int[] arr4 = {3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3};
count.findCounts(arr4, arr4.Length);
int[] arr5 = {1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11};
count.findCounts(arr5, arr5.Length);
int[] arr6 = {11, 10, 9, 8, 7, 6,
5, 4, 3, 2, 1};
count.findCounts(arr6, arr6.Length);
}
}
// This code is contributed by ChitraNayal
Javascript
<script>
// Javascript program to print frequencies
// of all array elements in O(1) extra
// space and O(n) time
// Function to find counts of all elements
// present in arr[0..n-1]. The array
// elements must be range from 1 to n
function findCounts(arr, n)
{
// Traverse all array elements
let i = 0;
while (i < n)
{
// If this element is already processed,
// then nothing to do
if (arr[i] <= 0)
{
i++;
continue;
}
// Find index corresponding to this element
// For example, index for 5 is 4
let elementIndex = arr[i] - 1;
// If the elementIndex has an element that
// is not processed yet, then first store
// that element to arr[i] so that we don't
// lose anything.
if (arr[elementIndex] > 0)
{
arr[i] = arr[elementIndex];
// After storing arr[elementIndex],
// change it to store initial count
// of 'arr[i]'
arr[elementIndex] = -1;
}
else
{
// If this is NOT first occurrence
// of arr[i], then decrement its count.
arr[elementIndex]--;
// And initialize arr[i] as 0 means
// the element 'i+1' is not seen so far
arr[i] = 0;
i++;
}
}
document.write("<br>Below are counts of all elements<br>");
for(let j = 0; j < n; j++)
document.write(j+1 + "->" +
Math.abs(arr[j]) + "<br>");
}
// Driver code
let arr = [ 2, 3, 3, 2, 5 ];
findCounts(arr, arr.length);
let arr1 = [ 1 ];
findCounts(arr1, arr1.length);
let arr3 = [ 4, 4, 4, 4 ];
findCounts(arr3, arr3.length);
let arr2 = [ 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1 ];
findCounts(arr2, arr2.length);
let arr4 = [ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 ];
findCounts(arr4, arr4.length);
let arr5 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];
findCounts(arr5, arr5.length);
let arr6 = [ 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ];
findCounts(arr6, arr6.length);
// This code is contributed by unknown2108
</script>
Producción
Below are counts of all elements 1 -> 0 2 -> 2 3 -> 2 4 -> 0 5 -> 1 Below are counts of all elements 1 -> 1 Below are counts of all elements 1 -> 0 2 -> 0 3 -> 0 4 -> 4 Below are counts of all elements 1 -> 3 2 -> 0 3 -> 2 4 -> 0 5 -> 2 6 -> 0 7 -> 2 8 -> 0 9 -> 2 10 -> 0 11 -> 0 Below are counts of all elements 1 -> 0 2 -> 0 3 -> 11 4 -> 0 5 -> 0 6 -> 0 7 -> 0 8 -> 0 9 -> 0 10 -> 0 11 -> 0 Below are counts of all elements 1 -> 1 2 -> 1 3 -> 1 4 -> 1 5 -> 1 6 -> 1 7 -> 1 8 -> 1 9 -> 1 10 -> 1 11 -> 1 Below are counts of all elements 1 -> 1 2 -> 1 3 -> 1 4 -> 1 5 -> 1 6 -> 1 7 -> 1 8 -> 1 9 -> 1 10 -> 1 11 -> 1
- Análisis de Complejidad:
- Complejidad temporal: O(n).
Como un solo recorrido de la array toma O (n) tiempo. - Complejidad espacial: O(1).
Ya que no se necesita espacio adicional.
- Complejidad temporal: O(n).
Método 3 : agregando ‘n’ para realizar un seguimiento de los recuentos.
- Enfoque: Todos los elementos de la array son de 1 a n. Reduzca cada elemento en 1. Los elementos de la array ahora están en el rango de 0 a n-1, por lo que se puede decir que para cada índice i, floor(array[i]/n) = 0 .
Entonces, como se dijo anteriormente, la idea es atravesar la array dada, usar elementos como índice y almacenar sus conteos en el índice. Considere el enfoque básico, se necesita un Hashmap de tamaño n y la array también es de tamaño n. Entonces, la array se puede usar como un mapa hash, pero la diferencia es que, en lugar de reemplazar elementos, agregue n al índice [i] de la array .
Entonces, después de actualizar, el arreglo[i]%n dará el i-ésimo elemento y el arreglo[i]/n dará la frecuencia de i+1.
- Algoritmo:
- Recorra la array de principio a fin y reduzca todos los elementos en 1.
- De nuevo, recorra la array de principio a fin.
- Para cada elemento array[i]%n actualizar array[array[i]%n] , es decir, array[array[i]%n]++
- Recorra la array de principio a fin e imprima i + 1 como valor y array[i]/n como frecuencia.
- Implementación:
C++
// C++ program to print frequencies of all array
// elements in O(1) extra space and O(n) time
#include<bits/stdc++.h>
using namespace std;
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
void printfrequency(int arr[],int n)
{
// Subtract 1 from every element so that the elements
// become in range from 0 to n-1
for (int j =0; j<n; j++)
arr[j] = arr[j]-1;
// Use every element arr[i] as index and add 'n' to
// element present at arr[i]%n to keep track of count of
// occurrences of arr[i]
for (int i=0; i<n; i++)
arr[arr[i]%n] = arr[arr[i]%n] + n;
// To print counts, simply print the number of times n
// was added at index corresponding to every element
for (int i =0; i<n; i++)
cout << i + 1 << " -> " << arr[i]/n << endl;
}
// Driver program to test above function
int main()
{
int arr[] = {2, 3, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
printfrequency(arr,n);
return 0;
}
Java
class CountFrequency
{
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
void printfrequency(int arr[], int n)
{
// Subtract 1 from every element so that the elements
// become in range from 0 to n-1
for (int j = 0; j < n; j++)
arr[j] = arr[j] - 1;
// Use every element arr[i] as index and add 'n' to
// element present at arr[i]%n to keep track of count of
// occurrences of arr[i]
for (int i = 0; i < n; i++)
arr[arr[i] % n] = arr[arr[i] % n] + n;
// To print counts, simply print the number of times n
// was added at index corresponding to every element
for (int i = 0; i < n; i++)
System.out.println(i + 1 + "->" + arr[i] / n);
}
// Driver program to test above functions
public static void main(String[] args)
{
CountFrequency count = new CountFrequency();
int arr[] = {2, 3, 3, 2, 5};
int n = arr.length;
count.printfrequency(arr, n);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python 3 program to print frequencies # of all array elements in O(1) extra # space and O(n) time # Function to find counts of all elements # present in arr[0..n-1]. The array # elements must be range from 1 to n def printfrequency(arr, n): # Subtract 1 from every element so that # the elements become in range from 0 to n-1 for j in range(n): arr[j] = arr[j] - 1 # Use every element arr[i] as index # and add 'n' to element present at # arr[i]%n to keep track of count of # occurrences of arr[i] for i in range(n): arr[arr[i] % n] = arr[arr[i] % n] + n # To print counts, simply print the # number of times n was added at index # corresponding to every element for i in range(n): print(i + 1, "->", arr[i] // n) # Driver code arr = [2, 3, 3, 2, 5] n = len(arr) printfrequency(arr, n) # This code is contributed # by Shrikant13
C#
using System;
internal class CountFrequency
{
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
internal virtual void printfrequency(int[] arr, int n)
{
// Subtract 1 from every element so that the elements
// become in range from 0 to n-1
for (int j = 0; j < n; j++)
{
arr[j] = arr[j] - 1;
}
// Use every element arr[i] as index and add 'n' to
// element present at arr[i]%n to keep track of count of
// occurrences of arr[i]
for (int i = 0; i < n; i++)
{
arr[arr[i] % n] = arr[arr[i] % n] + n;
}
// To print counts, simply print the number of times n
// was added at index corresponding to every element
for (int i = 0; i < n; i++)
{
Console.WriteLine(i + 1 + "->" + arr[i] / n);
}
}
// Driver program to test above functions
public static void Main(string[] args)
{
CountFrequency count = new CountFrequency();
int[] arr = new int[] {2, 3, 3, 2, 5};
int n = arr.Length;
count.printfrequency(arr, n);
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to print
// frequencies of all
// array elements in O(1)
// extra space and O(n) time
// Function to find counts
// of all elements present
// in arr[0..n-1]. The array
// elements must be range
// from 1 to n
function printfrequency($arr,$n)
{
// Subtract 1 from every
// element so that the
// elements become in
// range from 0 to n-1
for ($j = 0; $j < $n; $j++)
$arr[$j] = $arr[$j] - 1;
// Use every element arr[i]
// as index and add 'n' to
// element present at arr[i]%n
// to keep track of count of
// occurrences of arr[i]
for ($i = 0; $i < $n; $i++)
$arr[$arr[$i] % $n] =
$arr[$arr[$i] % $n] + $n;
// To print counts, simply
// print the number of times
// n was added at index
// corresponding to every element
for ($i = 0; $i < $n; $i++)
echo $i + 1, " -> " ,
(int)($arr[$i] / $n) , "\n";
}
// Driver Code
$arr = array(2, 3, 3, 2, 5);
$n = sizeof($arr);
printfrequency($arr,$n);
// This code is contributed by ajit
?>
Javascript
<script>
// Function to find counts of all elements present in
// arr[0..n-1]. The array elements must be range from
// 1 to n
function printfrequency(arr, n)
{
// Subtract 1 from every element so that the elements
// become in range from 0 to n-1
for (let j = 0; j < n; j++)
arr[j] = arr[j] - 1;
// Use every element arr[i] as index and add 'n' to
// element present at arr[i]%n to keep track of count of
// occurrences of arr[i]
for (let i = 0; i < n; i++)
arr[arr[i] % n] = arr[arr[i] % n] + n;
// To print counts, simply print the number of times n
// was added at index corresponding to every element
for (let i = 0; i < n; i++)
document.write((i + 1) + " -> " + parseInt(arr[i] / n, 10) + "</br>");
}
let arr = [2, 3, 3, 2, 5];
let n = arr.length;
printfrequency(arr, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción
1 -> 0 2 -> 2 3 -> 2 4 -> 0 5 -> 1
- Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesitan dos recorridos de la array y un solo recorrido de la array lleva O (n) tiempo. - Complejidad espacial: O(1).
Ya que no se necesita espacio adicional.
- Complejidad temporal: O(n).
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