Dada una array arr[] y un entero K , la tarea es encontrar los K elementos de la array cuya diferencia absoluta con la mediana de la array sea máxima.
Nota: Si dos elementos tienen la misma diferencia, se tiene en cuenta el elemento máximo.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, k = 3
Salida: {5, 1, 4}
Explicación:
Mediana m = 3,
Diferencia de cada elemento de la array desde la mediana,
1 ==> diff (1-3) = 2
2 ==> diferencia(2-3) = 1
3 ==> diferencia(3-3) = 0
4 ==> diferencia(4-3) = 1
5 ==> diferencia(5 -3) = 2
Los primeros elementos K son 5, 1, 4 en esta array.Entrada: arr[] = {1, 2, 3}, K = 2
Salida: {3, 1}
Acercarse:
- Ordena la array y encuentra la mediana de la array
- Cree una array de diferencia para almacenar la diferencia de cada elemento con la mediana de la array ordenada.
- Los elementos de mayor diferencia serán los elementos de esquina de la array. Por lo tanto, inicialice los dos punteros como elementos de esquina de la array que es 0 y N – 1.
- Finalmente incluya los elementos del arreglo uno por uno con la máxima diferencia con la mediana.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find first K
// elements whose difference with the
// median of array is maximum
#include <bits/stdc++.h>
using namespace std;
// Function for calculating median
double findMedian(int a[], int n)
{
// check for even case
if (n % 2 != 0)
return (double)a[n/2];
return (double)(a[(n-1)/2] + a[n/2])/2.0;
}
// Function to find the K maximum absolute
// difference with the median of the array
void kStrongest(int arr[], int n, int k)
{
// Sort the array.
sort(arr, arr + n);
// Store median
double median = findMedian(arr, n);
int diff[n];
// Find and store difference
for (int i = 0; i < n; i++) {
diff[i] = abs(median - arr[i]);
}
int i = 0, j = n - 1;
while (k > 0) {
// If diff[i] is greater print it
// Else print diff[j]
if (diff[i] > diff[j]) {
cout << arr[i] << " ";
i++;
}
else {
cout << arr[j] << " ";
j--;
}
k--;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
kStrongest(arr, n, k);
return 0;
}
Java
// Java implementation to find first K
// elements whose difference with the
// median of array is maximum
import java.util.*;
class GFG{
// Function for calculating median
static double findMedian(int a[], int n)
{
// check for even case
if (n % 2 != 0)
return (double)a[n / 2];
return (double)(a[(n - 1) / 2] +
a[n / 2]) / 2.0;
}
// Function to find the K maximum absolute
// difference with the median of the array
static void kStrongest(int arr[], int n, int k)
{
// Sort the array.
Arrays.sort(arr);
// Store median
double median = findMedian(arr, n);
int []diff = new int[n];
// Find and store difference
for (int i = 0; i < n; i++)
{
diff[i] = (int)Math.abs(median - arr[i]);
}
int i = 0, j = n - 1;
while (k > 0)
{
// If diff[i] is greater print it
// Else print diff[j]
if (diff[i] > diff[j])
{
System.out.print(arr[i] + " ");
i++;
}
else
{
System.out.print(arr[j] + " ");
j--;
}
k--;
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int k = 3;
int n = arr.length;
kStrongest(arr, n, k);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to find first K # elements whose difference with the # median of array is maximum # Function for calculating median def findMedian(a, n): # Check for even case if (n % 2 != 0): return a[int(n / 2)] return (a[int((n - 1) / 2)] + a[int(n / 2)]) / 2.0 # Function to find the K maximum # absolute difference with the # median of the array def kStrongest(arr, n, k): # Sort the array arr.sort() # Store median median = findMedian(arr, n) diff = [0] * (n) # Find and store difference for i in range(n): diff[i] = abs(median - arr[i]) i = 0 j = n - 1 while (k > 0): # If diff[i] is greater print # it. Else print diff[j] if (diff[i] > diff[j]): print(arr[i], end = " ") i += 1 else: print(arr[j], end = " ") j -= 1 k -= 1 # Driver code arr = [ 1, 2, 3, 4, 5 ] k = 3 n = len(arr) kStrongest(arr, n, k) # This code is contributed by sanjoy_62
C#
// C# implementation to find first K
// elements whose difference with the
// median of array is maximum
using System;
class GFG{
// Function for calculating median
static double findMedian(int []a, int n)
{
// Check for even case
if (n % 2 != 0)
return (double)a[n / 2];
return (double)(a[(n - 1) / 2] +
a[n / 2]) / 2.0;
}
// Function to find the K maximum absolute
// difference with the median of the array
static void kStrongest(int []arr, int n,
int k)
{
// Sort the array.
Array.Sort(arr);
int i = 0;
// Store median
double median = findMedian(arr, n);
int []diff = new int[n];
// Find and store difference
for(i = 0; i < n; i++)
{
diff[i] = (int)Math.Abs(median - arr[i]);
}
int j = n - 1;
i = 0;
while (k > 0)
{
// If diff[i] is greater print it
// Else print diff[j]
if (diff[i] > diff[j])
{
Console.Write(arr[i] + " ");
i++;
}
else
{
Console.Write(arr[j] + " ");
j--;
}
k--;
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int k = 3;
int n = arr.Length;
kStrongest(arr, n, k);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript implementation to find first K
// elements whose difference with the
// median of array is maximum
// Function for calculating median
function findMedian(a, n)
{
// Check for even case
if (n % 2 != 0)
return a[Math.floor(n / 2)];
return (a[Math.floor((n - 1) / 2)] +
a[Math.floor(n / 2)]) / 2.0;
}
// Function to find the K maximum absolute
// difference with the median of the array
function kStrongest(arr, n, k)
{
// Sort the array.
arr.sort();
// Store median
let median = findMedian(arr, n);
let diff = Array.from({length: n}, (_, i) => 0);
// Find and store difference
for(let i = 0; i < n; i++)
{
diff[i] = Math.abs(median - arr[i]);
}
let i = 0, j = n - 1;
while (k > 0)
{
// If diff[i] is greater print it
// Else print diff[j]
if (diff[i] > diff[j])
{
document.write(arr[i] + " ");
i++;
}
else
{
document.write(arr[j] + " ");
j--;
}
k--;
}
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5 ];
let k = 3;
let n = arr.length;
kStrongest(arr, n, k);
// This code is contributed by susmitakundugoaldanga
</script>
Producción:
5 1 4
Complejidad de tiempo: O(nlogn), donde nlogn es la complejidad de tiempo requerida para ordenar la array dada
Espacio auxiliar: O(n), espacio adicional utilizado para crear una array de diferencias