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>
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>
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
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