Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar todos los elementos de la array que aparecen más de (N/K) veces.
Ejemplos:
Entrada: arr[] = { 1, 2, 6, 6, 6, 6, 6, 10 }, K = 4
Salida: 6
Explicación:
La frecuencia de 6 en la array es mayor que N / K(= 2). Por lo tanto, la salida requerida es 6.Entrada: arr[] = { 3, 4, 4, 5, 5, 5, 5 }, K = 4
Salida: 4 5
Explicación:
La frecuencia de 4 en la array es mayor que N / K(= 1).
La frecuencia de 5 en la array es mayor que N / K(= 1).
Por lo tanto, la salida requerida es 4 5.
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento distinto de la array, contar su frecuencia y verificar si excede N / K o no. Si se encuentra que es cierto, imprima el elemento de la array.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque basado en clasificación: la idea es ordenar la array seguida de un recorrido de la array para contar la frecuencia de cada elemento distinto de la array al verificar si los elementos adyacentes son iguales o no. Si se encuentra que la frecuencia del elemento de la array es mayor que N / K , imprima el elemento de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all array elements
// whose frequency is greater than N / K
void NDivKWithFreq(int arr[], int N, int K)
{
// Sort the array, arr[]
sort(arr, arr + N);
// Traverse the array
for (int i = 0; i < N;) {
// Stores frequency of arr[i]
int cnt = 1;
// Traverse array elements which
// is equal to arr[i]
while ((i + 1) < N
&& arr[i] == arr[i + 1]) {
// Update cnt
cnt++;
// Update i
i++;
}
// If frequency of arr[i] is
// greater than (N / K)
if (cnt > (N / K)) {
cout << arr[i] << " ";
}
i++;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 4;
NDivKWithFreq(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to print all array elements
// whose frequency is greater than N / K
static void NDivKWithFreq(int arr[], int N, int K)
{
// Sort the array, arr[]
Arrays.sort(arr);
// Traverse the array
for (int i = 0; i < N;) {
// Stores frequency of arr[i]
int cnt = 1;
// Traverse array elements which
// is equal to arr[i]
while ((i + 1) < N
&& arr[i] == arr[i + 1]) {
// Update cnt
cnt++;
// Update i
i++;
}
// If frequency of arr[i] is
// greater than (N / K)
if (cnt > (N / K)) {
System.out.print(arr[i]+ " ");
}
i++;
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
int N = arr.length;
int K = 4;
NDivKWithFreq(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to print all array elements # whose frequency is greater than N / K def NDivKWithFreq(arr, N, K): # Sort the array, arr[] arr = sorted(arr) # Traverse the array i = 0 while i < N: # Stores frequency of arr[i] cnt = 1 # Traverse array elements which # is equal to arr[i] while ((i + 1) < N and arr[i] == arr[i + 1]): # Update cnt cnt += 1 # Update i i += 1 # If frequency of arr[i] is # greater than (N / K) if (cnt > (N // K)): print(arr[i], end = " ") i += 1 # Driver Code if __name__ == '__main__': arr = [ 1, 2, 2, 6, 6, 6, 6, 7, 10 ] N = len(arr) K = 4 NDivKWithFreq(arr, N, K) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to print all array elements
// whose frequency is greater than N / K
static void NDivKWithFreq(int[] arr, int N,
int K)
{
// Sort the array, arr[]
Array.Sort(arr);
// Traverse the array
for(int i = 0; i < N;)
{
// Stores frequency of arr[i]
int cnt = 1;
// Traverse array elements which
// is equal to arr[i]
while ((i + 1) < N &&
arr[i] == arr[i + 1])
{
// Update cnt
cnt++;
// Update i
i++;
}
// If frequency of arr[i] is
// greater than (N / K)
if (cnt > (N / K))
{
Console.Write(arr[i] + " ");
}
i++;
}
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
int N = arr.Length;
int K = 4;
NDivKWithFreq(arr, N, K);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for above approach
// Function to print all array elements
// whose frequency is greater than N / K
function NDivKWithFreq(arr, N, K)
{
// Sort the array, arr[]
arr.sort();
// Traverse the array
for (let i = 0; i < N;) {
// Stores frequency of arr[i]
let cnt = 1;
// Traverse array elements which
// is equal to arr[i]
while ((i + 1) < N
&& arr[i] == arr[i + 1]) {
// Update cnt
cnt++;
// Update i
i++;
}
// If frequency of arr[i] is
// greater than (N / K)
if (cnt > (N / K)) {
document.write(arr[i]+ " ");
}
i++;
}
}
// Driver Code
let arr = [1, 2, 2, 6, 6, 6, 6, 7, 10 ];
let N = arr.length;
let K = 4;
NDivKWithFreq(arr, N, K);
</script>
Producción:
6
Complejidad de tiempo: O(N * log 2 N)
Espacio auxiliar: O(1)
Enfoque basado en búsqueda binaria: el problema se puede resolver utilizando la técnica de búsqueda binaria . La idea es atravesar la array y contar la frecuencia de cada elemento distinto de la array calculando el límite superior de los elementos de la array. Finalmente, verifique si la frecuencia del elemento de la array es mayor que N / K o no. Si se encuentra que es cierto, imprima el elemento de la array. Siga los pasos a continuación para resolver el problema:
- Ordene la array , arr[] .
- Recorre la array usando la variable i y encuentra el límite superior de arr[i] , por ejemplo, X y verifica si (x – i) es mayor que N / K o no. Si se encuentra que es cierto, imprima el arr[i] .
- Finalmente, actualice i = X .
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to+ find the upper_bound of
// an array element
int upperBound(int arr[], int N, int K)
{
// Stores minimum index
// in which K lies
int l = 0;
// Stores maximum index
// in which K lies
int r = N;
// Calculate the upper
// bound of K
while (l < r) {
// Stores mid element
// of l and r
int mid = (l + r) / 2;
// If arr[mid] is less
// than or equal to K
if (arr[mid] <= K) {
// Right subarray
l = mid + 1;
}
else {
// Left subarray
r = mid;
}
}
return l;
}
// Function to print all array elements
// whose frequency is greater than N / K
void NDivKWithFreq(int arr[], int N, int K)
{
// Sort the array arr[]
sort(arr, arr + N);
// Stores index of
// an array element
int i = 0;
// Traverse the array
while (i < N) {
// Stores upper bound of arr[i]
int X = upperBound(arr, N, arr[i]);
// If frequency of arr[i] is
// greater than N / 4
if ((X - i) > N / 4) {
cout << arr[i] << " ";
}
// Update i
i = X;
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
int K = 4;
// Function Call
NDivKWithFreq(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to+ find the upper_bound of
// an array element
static int upperBound(int arr[], int N, int K)
{
// Stores minimum index
// in which K lies
int l = 0;
// Stores maximum index
// in which K lies
int r = N;
// Calculate the upper
// bound of K
while (l < r)
{
// Stores mid element
// of l and r
int mid = (l + r) / 2;
// If arr[mid] is less
// than or equal to K
if (arr[mid] <= K)
{
// Right subarray
l = mid + 1;
}
else
{
// Left subarray
r = mid;
}
}
return l;
}
// Function to print all array elements
// whose frequency is greater than N / K
static void NDivKWithFreq(int arr[], int N, int K)
{
// Sort the array arr[]
Arrays.sort(arr);
// Stores index of
// an array element
int i = 0;
// Traverse the array
while (i < N)
{
// Stores upper bound of arr[i]
int X = upperBound(arr, N, arr[i]);
// If frequency of arr[i] is
// greater than N / 4
if ((X - i) > N / 4)
{
System.out.print(arr[i] + " ");
}
// Update i
i = X;
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
// Size of array
int N = arr.length;
int K = 4;
// Function Call
NDivKWithFreq(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to implement # the above approach # Function to+ find the upper_bound of # an array element def upperBound(arr, N, K): # Stores minimum index # in which K lies l = 0; # Stores maximum index # in which K lies r = N; # Calculate the upper # bound of K while (l < r): # Stores mid element # of l and r mid = (l + r) // 2; # If arr[mid] is less # than or equal to K if (arr[mid] <= K): # Right subarray l = mid + 1; else: # Left subarray r = mid; return l; # Function to print all array elements # whose frequency is greater than N / K def NDivKWithFreq(arr, N, K): # Sort the array arr arr.sort(); # Stores index of # an array element i = 0; # Traverse the array while (i < N): # Stores upper bound of arr[i] X = upperBound(arr, N, arr[i]); # If frequency of arr[i] is # greater than N / 4 if ((X - i) > N // 4): print(arr[i], end=""); # Update i i = X; # Driver Code if __name__ == '__main__': # Given array arr arr = [1, 2, 2, 6, 6, 6, 6, 7, 10]; # Size of array N = len(arr); K = 4; # Function Call NDivKWithFreq(arr, N, K); # This code is contributed by 29AjayKumar
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to+ find the upper_bound of
// an array element
static int upperBound(int []arr, int N, int K)
{
// Stores minimum index
// in which K lies
int l = 0;
// Stores maximum index
// in which K lies
int r = N;
// Calculate the upper
// bound of K
while (l < r)
{
// Stores mid element
// of l and r
int mid = (l + r) / 2;
// If arr[mid] is less
// than or equal to K
if (arr[mid] <= K)
{
// Right subarray
l = mid + 1;
}
else
{
// Left subarray
r = mid;
}
}
return l;
}
// Function to print all array elements
// whose frequency is greater than N / K
static void NDivKWithFreq(int []arr, int N, int K)
{
// Sort the array arr[]
Array.Sort(arr);
// Stores index of
// an array element
int i = 0;
// Traverse the array
while (i < N)
{
// Stores upper bound of arr[i]
int X = upperBound(arr, N, arr[i]);
// If frequency of arr[i] is
// greater than N / 4
if ((X - i) > N / 4)
{
Console.Write(arr[i] + " ");
}
// Update i
i = X;
}
}
// Driver Code
public static void Main(string[] args)
{
// Given array arr[]
int []arr = { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
// Size of array
int N = arr.Length;
int K = 4;
// Function Call
NDivKWithFreq(arr, N, K);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program to implement
// the above approach
//function to sort the array
function sort(number)
{
var n= number.length;
for (i = 0; i < n; ++i)
{
for (j = i + 1; j < n; ++j)
{
if (number[i] > number[j])
{
a = number[i];
number[i] = number[j];
number[j] = a;
}
}
}
}
// Function to find the upper_bound of
// an array element
function upperBound( arr, N, K)
{
// Stores minimum index
// in which K lies
var l = 0;
// Stores maximum index
// in which K lies
var r = N;
// Calculate the upper
// bound of K
while (l < r) {
// Stores mid element
// of l and r
var mid = parseInt((l + r) / 2);
// If arr[mid] is less
// than or equal to K
if (arr[mid] <= K) {
// Right subarray
l = mid + 1;
}
else {
// Left subarray
r = mid;
}
}
return l;
}
// Function to print all array elements
// whose frequency is greater than N / K
function NDivKWithFreq(arr, N, K)
{
// Sort the array arr[]
sortt(arr);
// Stores index of
// an array element
var i = 0;
// Traverse the array
while (i < N) {
// Stores upper bound of arr[i]
var X = upperBound(arr, N, arr[i]);
// If frequency of arr[i] is
// greater than N / 4
if ((X - i) > parseInt(N / 4)) {
document.write( arr[i] + " ");
}
// Update i
i = X;
}
}
// Given array arr[]
var arr = [ 1, 2, 2, 6, 6, 6, 6, 7, 10 ];
// Size of array
var N = arr.length;
var K = 4;
// Function Call
NDivKWithFreq(arr, N, K);
//This code in contributed by SoumikMondal
</script>
Producción:
6
Complejidad de tiempo: O(N * log 2 N)
Espacio auxiliar: O(1)
Otro enfoque: usar 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:
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 atleast n/k times for it in mp: if mp[it] > x: print(it) # Driver code arr = [1, 2, 2, 6, 6, 6, 6, 7, 10] # Size of array n = len(arr) k = 4 printElements(arr, n, k) # This code is contributed by vikkycirus
Producción:
6
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar la frecuencia de cada elemento de array distinto en un Map . Finalmente, recorra el mapa y compruebe si su frecuencia es mayor que (N/K) o no. Si se encuentra que es cierto, imprima el elemento de la array. Consulte este artículo para la discusión de este enfoque.
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA