Dada una array A[] de tamaño mayor que el entero K , la tarea es encontrar el número total de elementos de la array que son mayores o iguales al doble de la mediana de K elementos finales en la array dada.
Ejemplos:
Entrada: A[] = {10, 20, 30, 40, 50}, K = 3
Salida: 1
Explicación:
Dado que K = 3, los únicos dos elementos que deben verificarse son {40, 50}.
Para 40, la mediana de 3 números finales {10, 20, 30} es 20.
Como 40 = 2 * 20, se cuenta 40.
Para el elemento 50, la mediana de 3 números finales {20, 30, 40} es 30.
Dado que 50 < 2 * 30, 50 no se cuenta.
Por lo tanto, la respuesta es 1.Entrada: A[] = {1, 2, 2, 4, 5}, K = 3
Salida: 2
Explicación:
Dado que K = 3, los únicos dos elementos considerados son {4, 5}.
Para 4, la mediana de 3 números finales {1, 2, 2} es 2.
Como 4 = 2 * 2, por lo tanto, se cuenta 4.
Para 5, la mediana de 3 números finales {2, 2, 4} es 2.
5 > 2 * 2, por lo que se cuenta 5.
Por lo tanto, la respuesta es 2.
Enfoque ingenuo:
siga los pasos a continuación para resolver el problema:
- Itere sobre la array dada desde K + 1 hasta el tamaño de la array y para cada elemento, agregue los K elementos anteriores de la array.
- Luego, encuentre la mediana y verifique si el elemento actual es igual o excede el doble del valor de la mediana. Si se determina que es cierto, aumente la cuenta .
- Finalmente. imprimir el conteo .
Complejidad de tiempo: O(N * K * log K)
Espacio auxiliar: O(1)
Enfoque eficiente:
Para optimizar el enfoque anterior, la idea es utilizar la técnica de conteo de frecuencia y ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Almacena las frecuencias de los elementos presentes en los primeros índices K.
- Iterar sobre la array desde (k + 1) th index hasta N th index y para cada iteración, disminuir la frecuencia del i – k th elemento donde i es el índice actual de los K elementos finales anteriores y aumentar el conteo de frecuencia de el elemento actual.
- Para cada iteración obtenga el valor de la mediana baja y la mediana alta que serán diferentes si la K es par. De lo contrario, será lo mismo.
- Inicialice una variable de conteo que contará la frecuencia. Siempre que se alcanza el piso ((k+1)/2) , el conteo da una mediana baja y, de manera similar, cuando el conteo llega al techo ((k+1)/2) , entonces da una mediana alta .
- Luego agregue el valor medio bajo y alto y verifique si el valor actual es mayor o igual que él o y, en consecuencia, actualice la respuesta.
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;
const int N = 2e5;
const int V = 500;
// Function to find the count of array elements >= twice the
// median of K trailing array elements
void solve(int n, int d, int input[])
{
int a[N];
// Stores frequencies
int cnt[V + 1];
// Stores the array elements
for (int i = 0; i < n; ++i)
a[i] = input[i];
int answer = 0;
// Count the frequencies of the array elements
for (int i = 0; i < d; ++i)
cnt[a[i]]++;
// Iterating from d to n-1 index means (d+1)th element
// to nth element
for (int i = d; i <= n - 1; ++i) {
// To check the median
int acc = 0;
int low_median = -1, high_median = -1;
// Iterate over the frequencies of the elements
for (int v = 0; v <= V; ++v) {
// Add the frequencies
acc += cnt[v];
// Check if the low_median value is obtained or
// not, if yes then do not change as it will be
// minimum
if (low_median == -1
&& acc >= int(floor((d + 1) / 2.0)))
low_median = v;
// Check if the high_median value is obtained or
// not, if yes then do not change it as it will
// be maximum
if (high_median == -1 && acc >= int(ceil((d + 1) / 2.0)))
high_median = v;
}
// Store 2 * median of K trailing elements
int double_median = low_median + high_median;
// If the current >= 2 * median
if (a[i] >= double_median)
answer++;
// Decrease the frequency for (k-1)-th element
cnt[a[i - d]]--;
// Increase the frequency of the current element
cnt[a[i]]++;
}
// Print the count
cout << answer << endl;
}
// Driver Code
int main()
{
int input[] = { 1, 2, 2, 4, 5 };
int n = sizeof input / sizeof input[0];
int k = 3;
solve(n, k, input);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C Program to implement the above approach
#include <stdio.h>
#include <math.h>
const int N = 2e5;
const int V = 500;
// Function to find the count of array elements >= twice the
// median of K trailing array elements
void solve(int n, int d, int input[])
{
int a[N];
// Stores frequencies
int cnt[V + 1];
// Stores the array elements
for (int i = 0; i < n; ++i)
a[i] = input[i];
int answer = 0;
// Count the frequencies of the array elements
for (int i = 0; i < d; ++i)
cnt[a[i]]++;
// Iterating from d to n-1 index means (d+1)th element
// to nth element
for (int i = d; i <= n - 1; ++i) {
// To check the median
int acc = 0;
int low_median = -1, high_median = -1;
// Iterate over the frequencies of the elements
for (int v = 0; v <= V; ++v) {
// Add the frequencies
acc += cnt[v];
// Check if the low_median value is obtained or
// not, if yes then do not change as it will be
// minimum
if (low_median == -1 && acc >= floor((d + 1) / 2.0))
low_median = v;
// Check if the high_median value is obtained or
// not, if yes then do not change it as it will
// be maximum
if (high_median == -1 && acc >= ceil((d + 1) / 2.0))
high_median = v;
}
// Store 2 * median of K trailing elements
int double_median = low_median + high_median;
// If the current >= 2 * median
if (a[i] >= double_median)
answer++;
// Decrease the frequency for (k-1)-th element
cnt[a[i - d]]--;
// Increase the frequency of the current element
cnt[a[i]]++;
}
// Print the count
printf("%d",answer);
}
// Driver Code
int main()
{
int input[] = { 1, 2, 2, 4, 5 };
int n = sizeof input / sizeof input[0];
int k = 3;
solve(n, k, input);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java Program to implement
// the above approach
class GFG{
static int N = (int) 2e5;
static int V = 500;
// Function to find the count of array
// elements >= twice the median of K
// trailing array elements
static void solve(int n, int d, int input[])
{
int []a = new int[N];
// Stores frequencies
int []cnt = new int[V + 1];
// Stores the array elements
for (int i = 0; i < n; ++i)
a[i] = input[i];
int answer = 0;
// Count the frequencies of the
// array elements
for (int i = 0; i < d; ++i)
cnt[a[i]]++;
// Iterating from d to n-1 index
// means (d+1)th element to nth element
for (int i = d; i <= n - 1; ++i)
{
// To check the median
int acc = 0;
int low_median = -1, high_median = -1;
// Iterate over the frequencies
// of the elements
for (int v = 0; v <= V; ++v)
{
// Add the frequencies
acc += cnt[v];
// Check if the low_median value is
// obtained or not, if yes then do
// not change as it will be minimum
if (low_median == -1
&& acc >= (int)(Math.floor((d + 1) / 2.0)))
low_median = v;
// Check if the high_median value is
// obtained or not, if yes then do not
// change it as it will be maximum
if (high_median == -1
&& acc >= (int)(Math.ceil((d + 1) / 2.0)))
high_median = v;
}
// Store 2 * median of K trailing elements
int double_median = low_median + high_median;
// If the current >= 2 * median
if (a[i] >= double_median)
answer++;
// Decrease the frequency for (k-1)-th element
cnt[a[i - d]]--;
// Increase the frequency of the
// current element
cnt[a[i]]++;
}
// Print the count
System.out.print(answer +"\n");
}
// Driver Code
public static void main(String[] args)
{
int input[] = { 1, 2, 2, 4, 5 };
int n = input.length;
int k = 3;
solve(n, k, input);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to implement # the above approach import math N = 200000 V = 500 # Function to find the count of array # elements >= twice the median of K # trailing array elements def solve(n, d, input1): a = [0] * N # Stores frequencies cnt = [0] * (V + 1) # Stores the array elements for i in range(n): a[i] = input1[i] answer = 0 # Count the frequencies of the # array elements for i in range(d): cnt[a[i]] += 1 # Iterating from d to n-1 index # means (d+1)th element to nth element for i in range(d, n): # To check the median acc = 0 low_median = -1 high_median = -1 # Iterate over the frequencies # of the elements for v in range(V + 1): # Add the frequencies acc += cnt[v] # Check if the low_median value is # obtained or not, if yes then do # not change as it will be minimum if (low_median == -1 and acc >= int(math.floor((d + 1) / 2.0))): low_median = v # Check if the high_median value is # obtained or not, if yes then do not # change it as it will be maximum if (high_median == -1 and acc >= int(math.ceil((d + 1) / 2.0))): high_median = v # Store 2 * median of K trailing elements double_median = low_median + high_median # If the current >= 2 * median if (a[i] >= double_median): answer += 1 # Decrease the frequency for (k-1)-th element cnt[a[i - d]] -= 1 # Increase the frequency of the # current element cnt[a[i]] += 1 # Print the count print(answer) # Driver Code if __name__ == "__main__": input1 = [ 1, 2, 2, 4, 5 ] n = len(input1) k = 3 solve(n, k, input1) # This code is contributed by chitranayal
C#
// C# Program to implement
// the above approach
using System;
class GFG{
static int N = (int) 2e5;
static int V = 500;
// Function to find the count of array
// elements >= twice the median of K
// trailing array elements
static void solve(int n, int d, int []input)
{
int []a = new int[N];
// Stores frequencies
int []cnt = new int[V + 1];
// Stores the array elements
for (int i = 0; i < n; ++i)
a[i] = input[i];
int answer = 0;
// Count the frequencies of the
// array elements
for (int i = 0; i < d; ++i)
cnt[a[i]]++;
// Iterating from d to n-1 index
// means (d+1)th element to nth element
for (int i = d; i <= n - 1; ++i)
{
// To check the median
int acc = 0;
int low_median = -1, high_median = -1;
// Iterate over the frequencies
// of the elements
for (int v = 0; v <= V; ++v)
{
// Add the frequencies
acc += cnt[v];
// Check if the low_median value is
// obtained or not, if yes then do
// not change as it will be minimum
if (low_median == -1 &&
acc >= (int)(Math.Floor((d + 1) / 2.0)))
low_median = v;
// Check if the high_median value is
// obtained or not, if yes then do not
// change it as it will be maximum
if (high_median == -1 &&
acc >= (int)(Math.Ceiling((d + 1) / 2.0)))
high_median = v;
}
// Store 2 * median of K trailing elements
int double_median = low_median + high_median;
// If the current >= 2 * median
if (a[i] >= double_median)
answer++;
// Decrease the frequency for (k-1)-th element
cnt[a[i - d]]--;
// Increase the frequency of the
// current element
cnt[a[i]]++;
}
// Print the count
Console.Write(answer + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int []input = { 1, 2, 2, 4, 5 };
int n = input.Length;
int k = 3;
solve(n, k, input);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript Program to implement
// the above approach
const N = 2e5;
const V = 500;
// Function to find the count of array
// elements >= twice the median of K
// trailing array elements
function solve(n, d, input)
{
let a = new Array(N);
// Stores frequencies
let cnt = new Array(V + 1);
// Stores the array elements
for(let i = 0; i < n; ++i)
a[i] = input[i];
let answer = 0;
// Count the frequencies of the
// array elements
for(let i = 0; i < d; ++i)
cnt[a[i]]++;
// Iterating from d to n-1 index
// means (d+1)th element to nth element
for(let i = d; i <= n - 1; ++i)
{
// To check the median
let acc = 0;
let low_median = -1, high_median = -1;
// Iterate over the frequencies
// of the elements
for(let v = 0; v <= V; ++v)
{
// Add the frequencies
acc += cnt[v];
// Check if the low_median value is
// obtained or not, if yes then do
// not change as it will be minimum
if (low_median == -1 &&
acc >= parseInt(Math.floor((d + 1) / 2.0)))
low_median = v;
// Check if the high_median value is
// obtained or not, if yes then do not
// change it as it will be maximum
if (high_median == -1 &&
acc >= parseInt(Math.ceil((d + 1) / 2.0)))
high_median = v;
}
// Store 2 * median of K trailing elements
let double_median = low_median + high_median;
// If the current >= 2 * median
if (a[i] >= double_median)
answer++;
// Decrease the frequency for (k-1)-th element
cnt[a[i - d]]--;
// Increase the frequency of the
// current element
cnt[a[i]]++;
}
// Print the count
document.write(answer);
}
// Driver Code
let input = [ 1, 2, 2, 4, 5 ];
let n = input.length;
let k = 3;
solve(n, k, input);
// This code is contributed by subham348
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)