Dado un arreglo arr[] que consta de N enteros y un entero positivo M , la tarea es encontrar el número de elementos del arreglo que ocurren al menos M veces.
Ejemplos:
Entrada: arr[] = {2, 3, 2, 2, 3, 5, 6, 3}, M = 2
Salida: 2 3
Explicación:
En la array dada arr[], el elemento que aparece al menos M número de los tiempos son {2, 3}.Entrada: arr[] = { 1, 32, 2, 1, 33, 5, 1, 5 }, M = 2
Salida: 1 5
Enfoque ingenuo: el enfoque más simple para resolver el problema es el siguiente:
- Atraviesa la array de izquierda a derecha
- Compruebe si un elemento ya apareció en el recorrido anterior o no. Si apareció, verifique el siguiente elemento. De lo contrario, vuelva a atravesar la array desde la i-ésima posición hasta la (n – 1)-ésima posición.
- Si la frecuencia es >= M . Imprime el elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of array
// elements with frequency at least M
void printElements(int arr[], int N, int M)
{
// Traverse the array
for (int i = 0; i < N; i++) {
int j;
for (j = i - 1; j >= 0; j--) {
if (arr[i] == arr[j])
break;
}
// If the element appeared before
if (j >= 0)
continue;
// Count frequency of the element
int freq = 0;
for (j = i; j < N; j++) {
if (arr[j] == arr[i])
freq++;
}
if (freq >= M)
cout << arr[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 2, 2, 3, 5, 6, 3 };
int M = 2;
int N = sizeof(arr) / sizeof(arr[0]);
printElements(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the number of array
// elements with frequency at least M
static void printElements(int[] arr, int N, int M)
{
// Traverse the array
for(int i = 0; i < N; i++)
{
int j;
for(j = i - 1; j >= 0; j--)
{
if (arr[i] == arr[j])
break;
}
// If the element appeared before
if (j >= 0)
continue;
// Count frequency of the element
int freq = 0;
for(j = i; j < N; j++)
{
if (arr[j] == arr[i])
freq++;
}
if (freq >= M)
System.out.print(arr[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 3, 2, 2, 3, 5, 6, 3 };
int M = 2;
int N = arr.length;
printElements(arr, N, M);
}
}
// This code is contributed by subhammahato348
Python3
# Python3 program for the above approach # Function to find the number of array # elements with frequency at least M def printElements(arr, N, M): # Traverse the array for i in range(N): j = i - 1 while j >= 0: if (arr[i] == arr[j]): break j -= 1 # If the element appeared before if (j >= 0): continue # Count frequency of the element freq = 0 for j in range(i, N): if (arr[j] == arr[i]): freq += 1 if (freq >= M): print(arr[i], end = " ") # Driver Code arr = [ 2, 3, 2, 2, 3, 5, 6, 3 ] M = 2 N = len(arr) printElements(arr, N, M) # This code is contributed by rohitsingh07052
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the number of array
// elements with frequency at least M
static void printElements(int[] arr, int N, int M)
{
// Traverse the array
for(int i = 0; i < N; i++)
{
int j;
for(j = i - 1; j >= 0; j--)
{
if (arr[i] == arr[j])
break;
}
// If the element appeared before
if (j >= 0)
continue;
// Count frequency of the element
int freq = 0;
for(j = i; j < N; j++)
{
if (arr[j] == arr[i])
freq++;
}
if (freq >= M)
Console.Write(arr[i] + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 3, 2, 2, 3, 5, 6, 3 };
int M = 2;
int N = arr.Length;
printElements(arr, N, M);
}
}
// This code is contributed by subham348
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of array
// elements with frequency at least M
function printElements(arr, N, M)
{
// Traverse the array
for (let i = 0; i < N; i++) {
let j;
for (j = i - 1; j >= 0; j--) {
if (arr[i] == arr[j])
break;
}
// If the element appeared before
if (j >= 0)
continue;
// Count frequency of the element
let freq = 0;
for (j = i; j < N; j++) {
if (arr[j] == arr[i])
freq++;
}
if (freq >= M)
document.write(arr[i] + " ");
}
}
// Driver Code
let arr = [ 2, 3, 2, 2, 3, 5, 6, 3 ];
let M = 2;
let N = arr.length;
printElements(arr, N, M);
// This code is contributed by subham348.
</script>
Producción
2 3
Enfoque: el problema dado se puede resolver almacenando las frecuencias de los elementos de la array en un HashMap , digamos M , e imprima todos los elementos en el mapa que tengan una frecuencia de al menos M.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of array
// elements with frequency at least M
void printElements(int arr[], int N, int M)
{
// Stores the frequency of each
// array elements
unordered_map<int, int> freq;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency of
// current array element
freq[arr[i]]++;
}
// Traverse the map and print array
// elements occurring at least M times
for (auto it : freq) {
if (it.second >= M) {
cout << it.first << " ";
}
}
return;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 2, 2,
3, 5, 6, 3 };
int M = 2;
int N = sizeof(arr) / sizeof(arr[0]);
printElements(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function to find the number of array
// elements with frequency at least M
static void printElements(int arr[], int N, int M)
{
// Stores the frequency of each
// array elements
HashMap<Integer, Integer> freq = new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update frequency of
// current array element
freq.put(arr[i],
freq.getOrDefault(arr[i], 0) + 1);
}
// Traverse the map and print array
// elements occurring at least M times
for (int key : freq.keySet())
{
if (freq.get(key) >= M) {
System.out.print(key + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 2, 2, 3, 5, 6, 3 };
int M = 2;
int N = arr.length;
printElements(arr, N, M);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach
# Function to find the number of array
# elements with frequency at least M
def printElements(arr, N, M):
# Stores the frequency of each
# array elements
freq = {}
# Traverse the array
for i in arr:
# Update frequency of
# current array element
freq[i] = freq.get(i, 0) + 1
# Traverse the map and print array
# elements occurring at least M times
for it in freq:
if (freq[it] >= M):
print(it, end = " ")
return
# Driver Code
if __name__ == '__main__':
arr = [2, 3, 2, 2, 3, 5, 6, 3]
M = 2
N = len(arr)
printElements(arr, N, M)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the number of array
// elements with frequency at least M
static void printElements(int []arr, int N, int M)
{
// Stores the frequency of each
// array elements
Dictionary<int,
int> freq = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency of
// current array element
if (freq.ContainsKey(arr[i]))
freq[arr[i]] += 1;
else
freq[arr[i]] = 1;
}
// Traverse the map and print array
// elements occurring at least M times
foreach(var item in freq)
{
if (item.Value >= M)
{
Console.Write(item.Key + " ");
}
}
return;
}
// Driver Code
public static void Main()
{
int []arr = { 2, 3, 2, 2,
3, 5, 6, 3 };
int M = 2;
int N = arr.Length;
printElements(arr, N, M);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of array
// elements with frequency at least M
function printElements(arr, N, M) {
// Stores the frequency of each
// array elements
let freq = new Map();
// Traverse the array
for (let i = 0; i < N; i++) {
// Update frequency of
// current array element
freq[arr[i]]++;
if (freq.has(arr[i])) {
freq.set(arr[i], freq.get(arr[i]) + 1)
} else {
freq.set(arr[i], 1)
}
}
// Traverse the map and print array
// elements occurring at least M times
for (let it of freq) {
if (it[1] >= M) {
document.write(it[0] + " ");
}
}
return;
}
// Driver Code
let arr = [2, 3, 2, 2,
3, 5, 6, 3];
let M = 2;
let N = arr.length;
printElements(arr, N, M);
// This code is contributed by gfgking.
</script>
Producción
2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
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 al menos m veces.
A continuación se muestra la implementación:
Python3
# Python3 implementation from collections import Counter # Function to find the number of array # elements with frequency at least M def printElements(arr, M): # Counting frequency of every element using Counter mp = Counter(arr) # Traverse the map and print all # the elements with occurrence atleast m times for it in mp: if mp[it] >= M: print(it, end=" ") # Driver code arr = [2, 3, 2, 2, 3, 5, 6, 3] M = 2 printElements(arr, M) # This code is contributed by vikkycirus
Producción
2 3
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por patelajeet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA