Dada una array de tamaño n, busque todos los elementos de la array que aparecen más de n/k veces. Por ejemplo, si las arrays de entrada son {3, 1, 2, 2, 1, 2, 3, 3} y k es 4, entonces la salida debería ser [2, 3]. Tenga en cuenta que el tamaño de la array es 8 (o n = 8), por lo que debemos encontrar todos los elementos que aparecen más de 2 (u 8/4) veces. Hay dos elementos que aparecen más de dos veces, el 2 y el 3.
Un método simple es elegir todos los elementos uno por uno. Para cada elemento seleccionado, cuente sus ocurrencias recorriendo la array, si el conteo es mayor que n/k, luego imprima el elemento. La complejidad temporal de este método sería O(n 2 .
C++
// C++ code to find elements whose
// frequency yis more than n/k
#include<bits/stdc++.h>
using namespace std;
void morethanNbyK(int arr[], int n, int k)
{
int x = n / k;
// unordered_map initialization
unordered_map<int, int> freq;
for(int i = 0; i < n; i++)
{
freq[arr[i]]++;
}
// Traversing the map
for(auto i : freq)
{
// Checking if value of a key-value pair
// is greater than x (where x=n/k)
if (i.second > x)
{
// Print the key of whose value
// is greater than x
cout << i.first << endl;
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 3, 5,
4, 2, 2, 3, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
morethanNbyK(arr, n, k);
return 0;
}
// This code is contributed by chayandas018
Java
// Java Code to find elements whose
// frequency yis more than n/k
import java.util.*;
public class Main
{
public static void morethanNdK(int a[], int n, int k)
{
int x = n / k;
// Hash map initialization
HashMap<Integer, Integer> y = new HashMap<>();
// count the frequency of each element.
for (int i = 0; i < n; i++)
{
// is element doesn't exist in hash table
if (!y.containsKey(a[i]))
y.put(a[i], 1);
// if element does exist in the hash table
else
{
int count = y.get(a[i]);
y.put(a[i], count + 1);
}
}
// iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
for (Map.Entry m : y.entrySet())
{
Integer temp = (Integer)m.getValue();
if (temp > x)
System.out.println(m.getKey());
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = new int[] { 1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1 };
int n = 12;
int k = 4;
morethanNdK(a, n, k);
}
}
Python3
# Python3 code to find elements whose
# frequency yis more than n/k
def morethanNbyK(arr, n, k) :
x = n // k
# unordered_map initialization
freq = {}
for i in range(n) :
if arr[i] in freq :
freq[arr[i]] += 1
else :
freq[arr[i]] = 1
# Traversing the map
for i in freq :
# Checking if value of a key-value pair
# is greater than x (where x=n/k)
if (freq[i] > x) :
# Print the key of whose value
# is greater than x
print(i)
# Driver code
arr = [ 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 ]
n = len(arr)
k = 4
morethanNbyK(arr, n, k)
# This code is contributed by mohit kumar 29
C#
// C# code to find elements whose
// frequency yis more than n/k
using System;
using System.Collections.Generic;
class GFG{
public static void morethanNdK(int []a, int n,
int k)
{
int x = n / k;
// Hash map initialization
Dictionary<int,
int> y = new Dictionary<int,
int>();
// Count the frequency of each element.
for(int i = 0; i < n; i++)
{
// Is element doesn't exist in hash table
if (!y.ContainsKey(a[i]))
y.Add(a[i], 1);
// If element does exist in the hash table
else
{
int count = y[a[i]];
y[a[i]] = count + 1;
}
}
// Iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
foreach(KeyValuePair<int, int> m in y)
{
int temp = (int)m.Value;
if (temp > x)
Console.WriteLine(m.Key);
}
}
// Driver Code
public static void Main(String[] args)
{
int []a = new int[]{ 1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1 };
int n = 12;
int k = 4;
morethanNdK(a, n, k);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript Code to find elements whose
// frequency yis more than n/k
function morethanNdK(a,n,k)
{
let x = n / k;
// Hash map initialization
let y=new Map();
// count the frequency of each element.
for (let i = 0; i < n; i++)
{
// is element doesn't exist in hash table
if (!y.has(a[i]))
y.set(a[i], 1);
// if element does exist in the hash table
else
{
let count = y.get(a[i]);
y.set(a[i], count + 1);
}
}
// iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
for (let [key, value] of y.entries())
{
let temp = value;
if (temp > x)
document.write(key+"<br>");
}
}
let a=[1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1];
let n = 12;
let k = 4;
morethanNdK(a, n, k);
// This code is contributed by unknown2108
</script>
Recomendado: pruebe su enfoque en {IDE} primero, antes de pasar a la solución.
Una mejor solución es usar sorting . Primero, ordene todos los elementos usando un algoritmo O(nLogn). Una vez que se ordena la array, podemos encontrar todos los elementos necesarios en un escaneo lineal de la array. Entonces, la complejidad de tiempo general de este método es O (nLogn) + O (n), que es O (nLogn).
La siguiente es una interesante solución O(nk):
Podemos resolver el problema anterior en tiempo O(nk) usando espacio adicional O(k-1). Tenga en cuenta que nunca puede haber más de k-1 elementos en la salida (¿Por qué?). Hay principalmente tres pasos en este algoritmo.
1) Cree una array temporal de tamaño (k-1) para almacenar elementos y sus recuentos (los elementos de salida estarán entre estos elementos k-1). A continuación se muestra la estructura de los elementos de la array temporal.
struct eleCount {
int eent;
int count;
};
struct eleCount temp[];
Este paso lleva O(k) tiempo.
2) Recorra la array de entrada y actualice temp[] (agregar/eliminar un elemento o aumentar/disminuir el conteo) para cada elemento atravesado. La array temp[] almacena candidatos potenciales (k-1) en cada paso. Este paso toma tiempo O(nk).
3) Iterar a través de los posibles candidatos finales (k-1) (almacenados en temp[]). o cada elemento, verifique si realmente tiene más de n/k. Este paso toma tiempo O(nk).
El paso principal es el paso 2, ¿cómo mantener (k-1) candidatos potenciales en cada punto? Los pasos utilizados en el paso 2 son como el famoso juego: Tetris. Tratamos cada número como una pieza en Tetris, que cae en nuestra array temporal temp[]. Nuestra tarea es tratar de mantener el mismo número apilado en la misma columna (se incrementa el recuento en la array temporal).
C++
// C++ code to find elements whose
// frequency yis more than n/k
#include<bits/stdc++.h>
using namespace std;
void morethanNbyK(int arr[], int n, int k)
{
int x = n / k;
// unordered_map initialization
unordered_map<int, int> freq;
for(int i = 0; i < n; i++)
{
freq[arr[i]]++;
}
// Traversing the map
for(auto i : freq)
{
// Checking if value of a key-value pair
// is greater than x (where x=n/k)
if (i.second > x)
{
// Print the key of whose value
// is greater than x
cout << i.first << endl;
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 3, 5,
4, 2, 2, 3, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
morethanNbyK(arr, n, k);
return 0;
}
// This code is contributed by chayandas018
Java
// Java Code to find elements whose
// frequency yis more than n/k
import java.util.*;
public class Main
{
public static void morethanNdK(int a[], int n, int k)
{
int x = n / k;
// Hash map initialization
HashMap<Integer, Integer> y = new HashMap<>();
// count the frequency of each element.
for (int i = 0; i < n; i++)
{
// is element doesn't exist in hash table
if (!y.containsKey(a[i]))
y.put(a[i], 1);
// if element does exist in the hash table
else
{
int count = y.get(a[i]);
y.put(a[i], count + 1);
}
}
// iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
for (Map.Entry m : y.entrySet())
{
Integer temp = (Integer)m.getValue();
if (temp > x)
System.out.println(m.getKey());
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = new int[] { 1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1 };
int n = 12;
int k = 4;
morethanNdK(a, n, k);
}
}
Python3
# Python3 code to find elements whose
# frequency yis more than n/k
def morethanNbyK(arr, n, k) :
x = n // k
# unordered_map initialization
freq = {}
for i in range(n) :
if arr[i] in freq :
freq[arr[i]] += 1
else :
freq[arr[i]] = 1
# Traversing the map
for i in freq :
# Checking if value of a key-value pair
# is greater than x (where x=n/k)
if (freq[i] > x) :
# Print the key of whose value
# is greater than x
print(i)
# Driver code
arr = [ 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 ]
n = len(arr)
k = 4
morethanNbyK(arr, n, k)
# This code is contributed by mohit kumar 29
C#
// C# code to find elements whose
// frequency yis more than n/k
using System;
using System.Collections.Generic;
class GFG{
public static void morethanNdK(int []a, int n,
int k)
{
int x = n / k;
// Hash map initialization
Dictionary<int,
int> y = new Dictionary<int,
int>();
// Count the frequency of each element.
for(int i = 0; i < n; i++)
{
// Is element doesn't exist in hash table
if (!y.ContainsKey(a[i]))
y.Add(a[i], 1);
// If element does exist in the hash table
else
{
int count = y[a[i]];
y[a[i]] = count + 1;
}
}
// Iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
foreach(KeyValuePair<int, int> m in y)
{
int temp = (int)m.Value;
if (temp > x)
Console.WriteLine(m.Key);
}
}
// Driver Code
public static void Main(String[] args)
{
int []a = new int[]{ 1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1 };
int n = 12;
int k = 4;
morethanNdK(a, n, k);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript Code to find elements whose
// frequency yis more than n/k
function morethanNdK(a,n,k)
{
let x = n / k;
// Hash map initialization
let y=new Map();
// count the frequency of each element.
for (let i = 0; i < n; i++)
{
// is element doesn't exist in hash table
if (!y.has(a[i]))
y.set(a[i], 1);
// if lement does exist in the hash table
else
{
let count = y.get(a[i]);
y.set(a[i], count + 1);
}
}
// iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
for (let [key, value] of y.entries())
{
let temp = value;
if (temp > x)
document.write(key+"<br>");
}
}
let a=[1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1];
let n = 12;
let k = 4;
morethanNdK(a, n, k);
// This code is contributed by unknown2108
</script>
Consider k = 4, n = 9
Given array: 3 1 2 2 2 1 4 3 3
i = 0
3 _ _
temp[] has one element, 3 with count 1
i = 1
3 1 _
temp[] has two elements, 3 and 1 with
counts 1 and 1 respectively
i = 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 1 respectively.
i = 3
- - 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.
i = 4
- - 2
- - 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 3 respectively.
i = 5
- - 2
- 1 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 2 and 3 respectively.
Ahora surge la pregunta, qué hacer cuando temp[] está lleno y vemos un nuevo elemento: eliminamos la fila inferior de las pilas de elementos, es decir, disminuimos el recuento de cada elemento en 1 en temp[]. Ignoramos el elemento actual.
i = 6
- - 2
- 1 2
temp[] has two elements, 1 and 2 with
counts as 1 and 2 respectively.
i = 7
- 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.
i = 8
3 - 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 2, 1 and 2 respectively.
Finalmente, tenemos como máximo números k-1 en temp[]. Los elementos en temp son {3, 1, 2}. Tenga en cuenta que los conteos en temp[] son inútiles ahora, los conteos solo se necesitaban en el paso 2. Ahora debemos verificar si los conteos reales de elementos en temp[] son más de n/k (9/4) o no. Los elementos 3 y 2 tienen cuentas más de 9/4. Entonces imprimimos 3 y 2.
Tenga en cuenta que el algoritmo no pierde ningún elemento de salida. Puede haber dos posibilidades, muchas ocurrencias están juntas o distribuidas en la array. Si las ocurrencias están juntas, el conteo será alto y no llegará a 0. Si las ocurrencias están dispersas, entonces el elemento aparecerá nuevamente en temp[]. A continuación se muestra la implementación del algoritmo anterior.
C++
// A C++ program to print elements with count more than n/k
#include <iostream>
using namespace std;
// A structure to store an element and its current count
struct eleCount {
int e; // Element
int c; // Count
};
// Prints elements with more
// than n/k occurrences in arr[]
// of size n. If there are no
// such elements, then it prints
// nothing.
void moreThanNdK(int arr[], int n, int k)
{
// k must be greater than
// 1 to get some output
if (k < 2)
return;
/* Step 1: Create a temporary
array (contains element
and count) of size k-1.
Initialize count of all
elements as 0 */
struct eleCount temp[k - 1];
for (int i = 0; i < k - 1; i++)
temp[i].c = 0;
/* Step 2: Process all
elements of input array */
for (int i = 0; i < n; i++)
{
int j;
/* If arr[i] is already present in
the element count array,
then increment its count
*/
for (j = 0; j < k - 1; j++)
{
if (temp[j].e == arr[i])
{
temp[j].c += 1;
break;
}
}
/* If arr[i] is not present in temp[] */
if (j == k - 1) {
int l;
/* If there is position available
in temp[], then place arr[i] in
the first available position and
set count as 1*/
for (l = 0; l < k - 1; l++)
{
if (temp[l].c == 0)
{
temp[l].e = arr[i];
temp[l].c = 1;
break;
}
}
/* If all the position in the
temp[] are filled, then decrease
count of every element by 1 */
if (l == k - 1)
for (l = 0; l < k-1; l++)
temp[l].c -= 1;
}
}
/*Step 3: Check actual counts of
* potential candidates in temp[]*/
for (int i = 0; i < k - 1; i++)
{
// Calculate actual count of elements
int ac = 0; // actual count
for (int j = 0; j < n; j++)
if (arr[j] == temp[i].e)
ac++;
// If actual count is more than n/k,
// then print it
if (ac > n / k)
cout << "Number:" << temp[i].e
<< " Count:" << ac << endl;
}
}
/* Driver code */
int main()
{
cout << "First Test\n";
int arr1[] = { 4, 5, 6, 7, 8, 4, 4 };
int size = sizeof(arr1) / sizeof(arr1[0]);
int k = 3;
moreThanNdK(arr1, size, k);
cout << "\nSecond Test\n";
int arr2[] = { 4, 2, 2, 7 };
size = sizeof(arr2) / sizeof(arr2[0]);
k = 3;
moreThanNdK(arr2, size, k);
cout << "\nThird Test\n";
int arr3[] = { 2, 7, 2 };
size = sizeof(arr3) / sizeof(arr3[0]);
k = 2;
moreThanNdK(arr3, size, k);
cout << "\nFourth Test\n";
int arr4[] = { 2, 3, 3, 2 };
size = sizeof(arr4) / sizeof(arr4[0]);
k = 3;
moreThanNdK(arr4, size, k);
return 0;
}
Java
// A Java program to print elements with count more than n/k
import java.util.*;
class GFG{
// A structure to store an element and its current count
static class eleCount {
int e; // Element
int c; // Count
};
// Prints elements with more
// than n/k occurrences in arr[]
// of size n. If there are no
// such elements, then it prints
// nothing.
static void moreThanNdK(int arr[], int n, int k)
{
// k must be greater than
// 1 to get some output
if (k < 2)
return;
/* Step 1: Create a temporary
array (contains element
and count) of size k-1.
Initialize count of all
elements as 0 */
eleCount []temp = new eleCount[k - 1];
for (int i = 0; i < k - 1; i++)
temp[i] = new eleCount();
for (int i = 0; i < k - 1; i++) {
temp[i].c = 0;
}
/* Step 2: Process all
elements of input array */
for (int i = 0; i < n; i++)
{
int j;
/* If arr[i] is already present in
the element count array,
then increment its count
*/
for (j = 0; j < k - 1; j++)
{
if (temp[j].e == arr[i])
{
temp[j].c += 1;
break;
}
}
/* If arr[i] is not present in temp[] */
if (j == k - 1) {
int l;
/* If there is position available
in temp[], then place arr[i] in
the first available position and
set count as 1*/
for (l = 0; l < k - 1; l++)
{
if (temp[l].c == 0)
{
temp[l].e = arr[i];
temp[l].c = 1;
break;
}
}
/* If all the position in the
temp[] are filled, then decrease
count of every element by 1 */
if (l == k - 1)
for (l = 0; l < k-1; l++)
temp[l].c -= 1;
}
}
/*Step 3: Check actual counts of
* potential candidates in temp[]*/
for (int i = 0; i < k - 1; i++)
{
// Calculate actual count of elements
int ac = 0; // actual count
for (int j = 0; j < n; j++)
if (arr[j] == temp[i].e)
ac++;
// If actual count is more than n/k,
// then print it
if (ac > n / k)
System.out.print("Number:" + temp[i].e
+ " Count:" + ac +"\n");
}
}
/* Driver code */
public static void main(String[] args)
{
System.out.print("First Test\n");
int arr1[] = { 4, 5, 6, 7, 8, 4, 4 };
int size = arr1.length;
int k = 3;
moreThanNdK(arr1, size, k);
System.out.print("\nSecond Test\n");
int arr2[] = { 4, 2, 2, 7 };
size = arr2.length;
k = 3;
moreThanNdK(arr2, size, k);
System.out.print("\nThird Test\n");
int arr3[] = { 2, 7, 2 };
size = arr3.length;
k = 2;
moreThanNdK(arr3, size, k);
System.out.print("\nFourth Test\n");
int arr4[] = { 2, 3, 3, 2 };
size = arr4.length;
k = 3;
moreThanNdK(arr4, size, k);
}
}
// This code contributed by Princi Singh .
Python3
# A Python3 program to print elements with
# count more than n/k
# Prints elements with more than n/k
# occurrences in arrof size n. If
# there are no such elements, then
# it prints nothing.
def moreThanNdK(arr, n, k):
# k must be greater than 1
# to get some output
if (k < 2):
return
# Step 1: Create a temporary array
# (contains element and count) of
# size k-1. Initialize count of all
# elements as 0
temp = [[0 for i in range(2)]
for i in range(k)]
for i in range(k - 1):
temp[i][0] = 0
# Step 2: Process all elements
# of input array
for i in range(n):
j = 0
# If arr[i] is already present in
# the element count array, then
# increment its count
while j < k - 1:
if (temp[j][1] == arr[i]):
temp[j][0] += 1
break
j += 1
# If arr[i] is not present in temp
if (j == k - 1):
l = 0
# If there is position available
# in temp[], then place arr[i]
# in the first available position
# and set count as 1*/
while l < k - 1:
if (temp[l][0] == 0):
temp[l][1] = arr[i]
temp[l][0] = 1
break
l += 1
# If all the position in the
# tempare filled, then decrease
# count of every element by 1
if (l == k - 1):
while l < k:
temp[l][0] -= 1
l += 1
# Step 3: Check actual counts
# of potential candidates in temp[]
for i in range(k - 1):
# Calculate actual count of elements
ac = 0 # Actual count
for j in range(n):
if (arr[j] == temp[i][1]):
ac += 1
# If actual count is more
# than n/k, then print
if (ac > n // k):
print("Number:",
temp[i][1],
" Count:", ac)
# Driver code
if __name__ == '__main__':
print("First Test")
arr1 = [4, 5, 6, 7, 8, 4, 4]
size = len(arr1)
k = 3
moreThanNdK(arr1, size, k)
print("Second Test")
arr2 = [4, 2, 2, 7]
size = len(arr2)
k = 3
moreThanNdK(arr2, size, k)
print("Third Test")
arr3 = [2, 7, 2]
size = len(arr3)
k = 2
moreThanNdK(arr3, size, k)
print("Fourth Test")
arr4 = [2, 3, 3, 2]
size = len(arr4)
k = 3
moreThanNdK(arr4, size, k)
# This code is contributed by mohit kumar 29
C#
// A C# program to print elements
// with count more than n/k
using System;
class GFG
{
// A structure to store an element
// and its current count
public class eleCount {
public int e; // Element
public int c; // Count
};
// Prints elements with more
// than n/k occurrences in []arr
// of size n. If there are no
// such elements, then it prints
// nothing.
static void moreThanNdK(int []arr, int n, int k)
{
// k must be greater than
// 1 to get some output
if (k < 2)
return;
/* Step 1: Create a temporary
array (contains element
and count) of size k-1.
Initialize count of all
elements as 0 */
eleCount []temp = new eleCount[k - 1];
for (int i = 0; i < k - 1; i++)
temp[i] = new eleCount();
for (int i = 0; i < k - 1; i++)
{
temp[i].c = 0;
}
/* Step 2: Process all
elements of input array */
for (int i = 0; i < n; i++)
{
int j;
/* If arr[i] is already present in
the element count array,
then increment its count
*/
for (j = 0; j < k - 1; j++)
{
if (temp[j].e == arr[i])
{
temp[j].c += 1;
break;
}
}
/* If arr[i] is not present in []temp */
if (j == k - 1)
{
int l;
/* If there is position available
in []temp, then place arr[i] in
the first available position and
set count as 1*/
for (l = 0; l < k - 1; l++)
{
if (temp[l].c == 0)
{
temp[l].e = arr[i];
temp[l].c = 1;
break;
}
}
/* If all the position in the
[]temp are filled, then decrease
count of every element by 1 */
if (l == k - 1)
for (l = 0; l < k-1; l++)
temp[l].c -= 1;
}
}
/*Step 3: Check actual counts of
* potential candidates in []temp*/
for (int i = 0; i < k - 1; i++)
{
// Calculate actual count of elements
int ac = 0; // actual count
for (int j = 0; j < n; j++)
if (arr[j] == temp[i].e)
ac++;
// If actual count is more than n/k,
// then print it
if (ac > n / k)
Console.Write("Number:" + temp[i].e
+ " Count:" + ac + "\n");
}
}
/* Driver code */
public static void Main(String[] args)
{
Console.Write("First Test\n");
int []arr1 = { 4, 5, 6, 7, 8, 4, 4 };
int size = arr1.Length;
int k = 3;
moreThanNdK(arr1, size, k);
Console.Write("\nSecond Test\n");
int []arr2 = { 4, 2, 2, 7 };
size = arr2.Length;
k = 3;
moreThanNdK(arr2, size, k);
Console.Write("\nThird Test\n");
int []arr3 = { 2, 7, 2 };
size = arr3.Length;
k = 2;
moreThanNdK(arr3, size, k);
Console.Write("\nFourth Test\n");
int []arr4 = { 2, 3, 3, 2 };
size = arr4.Length;
k = 3;
moreThanNdK(arr4, size, k);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// A JavaScript program to print elements with
// count more than n/k
// Prints elements with more than n/k
// occurrences in arrof size n. If
// there are no such elements, then
// it prints nothing.
function moreThanNdK(arr, n, k){
// k must be greater than 1
// to get some output
if (k < 2)
return;
// Step 1: Create a temporary array
// (contains element and count) of
// size k-1. Initialize count of all
// elements as 0
let temp = new Array(k-1);
for(let i = 0; i < k - 1; i++){
temp[i] = new Array(2);
temp[i][0] = 0;
}
// Step 2: Process all elements
// of input array
for(let i = 0; i < n; i++){
let j;
// If arr[i] is already present in
// the element count array, then
// increment its count
for (j = 0; j < k - 1; j++)
{
if (temp[j][1] == arr[i])
{
temp[j][0] += 1;
break;
}
}
// If arr[i] is not present in temp
if (j == k - 1){
let l;
// If there is position available
// in temp[], then place arr[i]
// in the first available position
// and set count as 1*/
for (l = 0; l < k - 1; l++)
{
if (temp[l][0] == 0)
{
temp[l][1] = arr[i];
temp[l][0] = 1;
break;
}
}
// If all the position in the
// tempare filled, then decrease
// count of every element by 1
if (l == k - 1)
for (l = 0; l < k-1; l++)
temp[l][0] -= 1;
}
}
// Step 3: Check actual counts
// of potential candidates in temp[]
for(let i = 0; i < k - 1; i++){
// Calculate actual count of elements
let ac = 0 // Actual count
for(let j = 0; j < n; j++){
if (arr[j] == temp[i][1])
ac++;
}
// If actual count is more
// than n/k, then print
if (ac > Math.floor(n/k))
document.write("Number: " + temp[i][1] +
" Count: " + ac,"</br>")
}
}
// Driver code
document.write("First Test","</br>")
let arr1 = [4, 5, 6, 7, 8, 4, 4]
let size = arr1.length
let k = 3
moreThanNdK(arr1, size, k)
document.write("Second Test","</br>")
let arr2 = [4, 2, 2, 7]
size = arr2.length
k = 3
moreThanNdK(arr2, size, k)
document.write("Third Test","</br>")
let arr3 = [2, 7, 2]
size = arr3.length
k = 2
moreThanNdK(arr3, size, k)
document.write("Fourth Test","</br>")
let arr4 = [2, 3, 3, 2]
size = arr4.length
k = 3
moreThanNdK(arr4, size, k)
// This code is contributed by shinjanpatra
</script>
Producción
First Test Number:4 Count:3 Second Test Number:2 Count:2 Third Test Number:2 Count:2 Fourth Test Number:2 Count:2 Number:3 Count:2
Complejidad de tiempo: O(nk)
Espacio auxiliar: O(k) Las
variaciones generalmente solicitadas de este problema son encontrar todos los elementos que aparecen n/3 veces o n/4 veces en O(n) complejidad de tiempo y O(1) espacio extra .
Otro enfoque:
Hashing también puede ser una solución eficiente. Con una buena función hash, podemos resolver el problema anterior en tiempo O(n) en promedio. El hashing requerido de espacio extra sería mayor que O(k). Además, el hashing no se puede usar para resolver las variaciones anteriores con O(1) espacio adicional.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ code to find elements whose
// frequency yis more than n/k
#include<bits/stdc++.h>
using namespace std;
void morethanNbyK(int arr[], int n, int k)
{
int x = n / k;
// unordered_map initialization
unordered_map<int, int> freq;
for(int i = 0; i < n; i++)
{
freq[arr[i]]++;
}
// Traversing the map
for(auto i : freq)
{
// Checking if value of a key-value pair
// is greater than x (where x=n/k)
if (i.second > x)
{
// Print the key of whose value
// is greater than x
cout << i.first << endl;
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 3, 5,
4, 2, 2, 3, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
morethanNbyK(arr, n, k);
return 0;
}
// This code is contributed by chayandas018
Java
// Java Code to find elements whose
// frequency yis more than n/k
import java.util.*;
public class Main
{
public static void morethanNdK(int a[], int n, int k)
{
int x = n / k;
// Hash map initialization
HashMap<Integer, Integer> y = new HashMap<>();
// count the frequency of each element.
for (int i = 0; i < n; i++)
{
// is element doesn't exist in hash table
if (!y.containsKey(a[i]))
y.put(a[i], 1);
// if lement does exist in the hash table
else
{
int count = y.get(a[i]);
y.put(a[i], count + 1);
}
}
// iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
for (Map.Entry m : y.entrySet())
{
Integer temp = (Integer)m.getValue();
if (temp > x)
System.out.println(m.getKey());
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = new int[] { 1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1 };
int n = 12;
int k = 4;
morethanNdK(a, n, k);
}
}
Python3
# Python3 code to find elements whose
# frequency yis more than n/k
def morethanNbyK(arr, n, k) :
x = n // k
# unordered_map initialization
freq = {}
for i in range(n) :
if arr[i] in freq :
freq[arr[i]] += 1
else :
freq[arr[i]] = 1
# Traversing the map
for i in freq :
# Checking if value of a key-value pair
# is greater than x (where x=n/k)
if (freq[i] > x) :
# Print the key of whose value
# is greater than x
print(i)
# Driver code
arr = [ 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 ]
n = len(arr)
k = 4
morethanNbyK(arr, n, k)
# This code is contributed by mohit kumar 29
C#
// C# code to find elements whose
// frequency yis more than n/k
using System;
using System.Collections.Generic;
class GFG{
public static void morethanNdK(int []a, int n,
int k)
{
int x = n / k;
// Hash map initialization
Dictionary<int,
int> y = new Dictionary<int,
int>();
// Count the frequency of each element.
for(int i = 0; i < n; i++)
{
// Is element doesn't exist in hash table
if (!y.ContainsKey(a[i]))
y.Add(a[i], 1);
// If element does exist in the hash table
else
{
int count = y[a[i]];
y[a[i]] = count + 1;
}
}
// Iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
foreach(KeyValuePair<int, int> m in y)
{
int temp = (int)m.Value;
if (temp > x)
Console.WriteLine(m.Key);
}
}
// Driver Code
public static void Main(String[] args)
{
int []a = new int[]{ 1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1 };
int n = 12;
int k = 4;
morethanNdK(a, n, k);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript Code to find elements whose
// frequency yis more than n/k
function morethanNdK(a,n,k)
{
let x = n / k;
// Hash map initialization
let y=new Map();
// count the frequency of each element.
for (let i = 0; i < n; i++)
{
// is element doesn't exist in hash table
if (!y.has(a[i]))
y.set(a[i], 1);
// if element does exist in the hash table
else
{
let count = y.get(a[i]);
y.set(a[i], count + 1);
}
}
// iterate over each element in the hash table
// and check their frequency, if it is more than
// n/k, print it.
for (let [key, value] of y.entries())
{
let temp = value;
if (temp > x)
document.write(key+"<br>");
}
}
let a=[1, 1, 2, 2, 3, 5, 4,
2, 2, 3, 1, 1, 1];
let n = 12;
let k = 4;
morethanNdK(a, n, k);
// This code is contributed by unknown2108
</script>
Producción
1 2
Método n.º 2: uso de las funciones integradas de Python:
- Cuente las frecuencias de cada elemento usando la función Counter() .
- Recorra la array de frecuencias e imprima todos los elementos que ocurren en más de n/k veces.
A continuación se muestra la implementación:
C++
// C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of array
// elements with frequency more than n/k times
void printElements(int arr[], int n, int k)
{
// Calculating n/k
int x = n / k;
// Counting frequency of every
// element using Counter
map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]] += 1;
// Traverse the map and print all
// the elements with occurrence
// more than n/k times
for (int it = 0; it < mp.size(); it++) {
if (mp[it] > x)
cout << (it) << endl;
}
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
printElements(arr, n, k);
}
// This code is contributed by ukasp.
Java
// Java implementation
import java.util.*;
class GFG {
// Function to find the number of array
// elements with frequency more than n/k times
static void printElements(int arr[], int n, int k)
{
// Calculating n/k
int x = n / k;
// Counting frequency of every
// element using Counter
TreeMap<Integer, Integer> mp
= new TreeMap<Integer, Integer>();
for (int i = 0; i < n; i++)
mp.put(arr[i],
mp.getOrDefault(arr[i], 0) + 1);
// Traverse the map and print all
// the elements with occurrence
// more than n/k times
for (Map.Entry m:mp.entrySet()) {
if ((int)m.getValue() > x)
System.out.println(m.getKey());
}
}
// Driver code
public static void main(String[] args)
{
int arr[]
= { 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 };
int n = arr.length;
int k = 4;
printElements(arr, n, k);
}
}
// This code is contributed by rajsanghavi9.
Python3
# Python3 implementation from collections import Counter # Function to find the number of array # elements with frequency more than n/k times def printElements(arr, n, k): # Calculating n/k x = n//k # Counting frequency of every # element using Counter mp = Counter(arr) # Traverse the map and print all # the elements with occurrence # more than n/k times for it in mp: if mp[it] > x: print(it) # Driver code arr = [1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1] n = len(arr) k = 4 printElements(arr, n, k) # This code is contributed by vikkycirus
C#
// C# implementation
using System;
using System.Collections.Generic;
public class GFG {
// Function to find the number of array
// elements with frequency more than n/k times
static void printElements(int[] arr, int n, int k)
{
// Calculating n/k
int x = n / k;
// Counting frequency of every
// element using Counter
Dictionary<int, int> mp
= new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (mp.ContainsKey(arr[i]))
mp[arr[i]] = mp[arr[i]] + 1;
else
mp.Add(arr[i], 1);
}
foreach(KeyValuePair<int, int> entry in mp)
{
if (entry.Value > x) {
Console.WriteLine(entry.Key);
}
}
// Traverse the map and print all
// the elements with occurrence
// more than n/k times
}
// Driver code
public static void Main(String[] args)
{
int[] arr
= { 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 };
int n = arr.Length;
int k = 4;
printElements(arr, n, k);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript implementation
// Function to find the number of array
// elements with frequency more than n/k times
function printElements(arr , n , k) {
// Calculating n/k
var x = parseInt(n / k);
// Counting frequency of every
// element using Counter
var mp = new Map();
for (var 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);
}
// Traverse the map and print all
// the elements with occurrence
// more than n/k times
for (var k of mp) {
if (parseInt(k[1]) > x)
document.write(k[0]+"<br/>");
}
}
// Driver code
var arr = [ 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 ];
var n = arr.length;
var k = 4;
printElements(arr, n, k);
// This code is contributed by gauravrajput1
</script>
Producción:
1 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p
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