Dada una array no ordenada arr[] de n enteros y un entero k , la tarea es encontrar el k-ésimo elemento más grande en el rango de índice dado [l, r]
Ejemplos:
Entrada: arr[] = {5, 3, 2, 4, 1}, k = 4, l = 1, r = 5
Salida: 4
4 será el cuarto elemento cuando se ordene arr[0…4].
Entrada: arr[] = {1, 4, 2, 3, 5, 7, 6}, k = 3, l = 3, r = 6
Salida: 5
Enfoque: una solución ingenua será ordenar los elementos en el rango y obtener el k-ésimo elemento más grande, la complejidad de tiempo de esa solución será nlog(n) para cada consulta. Podemos resolver cada consulta en log(n) usando una array de prefijos y una búsqueda binaria. Todo lo que tenemos que hacer es mantener una array de prefijos 2d en la que la i-ésima fila contendrá un número de elementos menor que igual a i en el mismo rango que en la array dada. Después de que la array de prefijos esté lista, todo lo que tenemos que hacer es una simple búsqueda binaria sobre la array de prefijos. Por lo tanto, la complejidad del tiempo se reduce drásticamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1001
static int prefix[MAX][MAX];
int ar[MAX];
// Function to calculate the prefix
void cal_prefix(int n, int arr[])
{
int i, j;
// Creating one based indexing
for (i = 0; i < n; i++)
ar[i + 1] = arr[i];
// Initializing and creating prefix array
for (i = 1; i <= 1000; i++) {
for (j = 0; j <= n; j++)
prefix[i][j] = 0;
for (j = 1; j <= n; j++) {
// Creating a prefix array for every
// possible value in a given range
prefix[i][j] = prefix[i][j - 1]
+ (int)(ar[j] <= i ? 1 : 0);
}
}
}
// Function to return the kth largest element
// in the index range [l, r]
int ksub(int l, int r, int n, int k)
{
int lo, hi, mid;
lo = 1;
hi = 1000;
// Binary searching through the 2d array
// and only checking the range in which
// the sub array is a part
while (lo + 1 < hi) {
mid = (lo + hi) / 2;
if (prefix[mid][r] - prefix[mid][l - 1] >= k)
hi = mid;
else
lo = mid + 1;
}
if (prefix[lo][r] - prefix[lo][l - 1] >= k)
hi = lo;
return hi;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 2, 3, 5, 7, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
// Creating the prefix array
// for the given array
cal_prefix(n, arr);
// Queries
int queries[][3] = { { 1, n, 1 },
{ 2, n - 2, 2 },
{ 3, n - 1, 3 } };
int q = sizeof(queries) / sizeof(queries[0]);
// Perform queries
for (int i = 0; i < q; i++)
cout << ksub(queries[i][0], queries[i][1],
n, queries[i][2])
<< endl;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 1001;
static int prefix[][] = new int[MAX][MAX];
static int ar[] = new int[MAX];
// Function to calculate the prefix
static void cal_prefix(int n, int arr[])
{
int i, j;
// Creating one based indexing
for (i = 0; i < n; i++)
ar[i + 1] = arr[i];
// Initializing and creating prefix array
for (i = 1; i <= 1000; i++)
{
for (j = 0; j <= n; j++)
prefix[i][j] = 0;
for (j = 1; j <= n; j++)
{
// Creating a prefix array for every
// possible value in a given range
prefix[i][j] = prefix[i][j - 1]
+ (int)(ar[j] <= i ? 1 : 0);
}
}
}
// Function to return the kth largest element
// in the index range [l, r]
static int ksub(int l, int r, int n, int k)
{
int lo, hi, mid;
lo = 1;
hi = 1000;
// Binary searching through the 2d array
// and only checking the range in which
// the sub array is a part
while (lo + 1 < hi)
{
mid = (lo + hi) / 2;
if (prefix[mid][r] - prefix[mid][l - 1] >= k)
hi = mid;
else
lo = mid + 1;
}
if (prefix[lo][r] - prefix[lo][l - 1] >= k)
hi = lo;
return hi;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 4, 2, 3, 5, 7, 6 };
int n = arr.length;
int k = 4;
// Creating the prefix array
// for the given array
cal_prefix(n, arr);
// Queries
int queries[][] = { { 1, n, 1 },
{ 2, n - 2, 2 },
{ 3, n - 1, 3 } };
int q = queries.length;
// Perform queries
for (int i = 0; i < q; i++)
System.out.println( ksub(queries[i][0], queries[i][1],
n, queries[i][2]));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach MAX = 1001 prefix = [[0 for i in range(MAX)] for j in range(MAX)] ar = [0 for i in range(MAX)] # Function to calculate the prefix def cal_prefix(n, arr): # Creating one based indexing for i in range(n): ar[i + 1] = arr[i] # Initializing and creating prefix array for i in range(1, 1001, 1): for j in range(n + 1): prefix[i][j] = 0 for j in range(1, n + 1): # Creating a prefix array for every # possible value in a given range if ar[j] <= i: k = 1 else: k = 0 prefix[i][j] = prefix[i][j - 1] + k # Function to return the kth largest element # in the index range [l, r] def ksub(l, r, n, k): lo = 1 hi = 1000 # Binary searching through the 2d array # and only checking the range in which # the sub array is a part while (lo + 1 < hi): mid = int((lo + hi) / 2) if (prefix[mid][r] - prefix[mid][l - 1] >= k): hi = mid else: lo = mid + 1 if (prefix[lo][r] - prefix[lo][l - 1] >= k): hi = lo return hi # Driver code if __name__ == '__main__': arr = [1, 4, 2, 3, 5, 7, 6] n = len(arr) k = 4 # Creating the prefix array # for the given array cal_prefix(n, arr) # Queries queries = [[1, n, 1], [2, n - 2, 2], [3, n - 1, 3]] q = len(queries) # Perform queries for i in range(q): print(ksub(queries[i][0], queries[i][1], n, queries[i][2])) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 1001;
static int[,] prefix = new int[MAX,MAX];
static int[] ar = new int[MAX];
// Function to calculate the prefix
static void cal_prefix(int n, int[] arr)
{
int i, j;
// Creating one based indexing
for (i = 0; i < n; i++)
ar[i + 1] = arr[i];
// Initializing and creating prefix array
for (i = 1; i <= 1000; i++)
{
for (j = 0; j <= n; j++)
prefix[i, j] = 0;
for (j = 1; j <= n; j++)
{
// Creating a prefix array for every
// possible value in a given range
prefix[i, j] = prefix[i, j - 1]
+ (int)(ar[j] <= i ? 1 : 0);
}
}
}
// Function to return the kth largest element
// in the index range [l, r]
static int ksub(int l, int r, int n, int k)
{
int lo, hi, mid;
lo = 1;
hi = 1000;
// Binary searching through the 2d array
// and only checking the range in which
// the sub array is a part
while (lo + 1 < hi)
{
mid = (lo + hi) / 2;
if (prefix[mid, r] - prefix[mid, l - 1] >= k)
hi = mid;
else
lo = mid + 1;
}
if (prefix[lo, r] - prefix[lo, l - 1] >= k)
hi = lo;
return hi;
}
// Driver code
static void Main()
{
int []arr = { 1, 4, 2, 3, 5, 7, 6 };
int n = arr.Length;
//int k = 4;
// Creating the prefix array
// for the given array
cal_prefix(n, arr);
// Queries
int [,]queries = { { 1, n, 1 },
{ 2, n - 2, 2 },
{ 3, n - 1, 3 } };
int q = queries.Length/queries.Rank-1;
// Perform queries
for (int i = 0; i < q; i++)
Console.WriteLine( ksub(queries[i,0], queries[i,1],
n, queries[i, 2]));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
$MAX = 101;
$prefix = array_fill(0, $MAX, array_fill(0, $MAX, 0));
$ar = array_fill(0, $MAX, 0);
// Function to calculate the prefix
function cal_prefix($n, $arr)
{
global $prefix,$ar,$MAX;
// Creating one based indexing
for ($i = 0; $i < $n; $i++)
$ar[$i + 1] = $arr[$i];
// Initializing and creating prefix array
for ($i = 1; $i <$MAX; $i++)
{
for ($j = 0; $j <= $n; $j++)
$prefix[$i][$j] = 0;
for ($j = 1; $j <= $n; $j++)
{
// Creating a prefix array for every
// possible value in a given range
$prefix[$i][$j] = $prefix[$i][$j - 1]
+ (int)($ar[$j] <= $i ? 1 : 0);
}
}
}
// Function to return the kth largest element
// in the index range [l, r]
function ksub($l, $r, $n, $k)
{
global $prefix, $ar, $MAX;
$lo = 1;
$hi = $MAX-1;
// Binary searching through the 2d array
// and only checking the range in which
// the sub array is a part
while ($lo + 1 < $hi)
{
$mid = (int)(($lo + $hi) / 2);
if ($prefix[$mid][$r] - $prefix[$mid][$l - 1] >= $k)
$hi = $mid;
else
$lo = $mid + 1;
}
if ($prefix[$lo][$r] - $prefix[$lo][$l - 1] >= $k)
$hi = $lo;
return $hi;
}
// Driver code
$arr = array( 1, 4, 2, 3, 5, 7, 6 );
$n = count($arr);
$k = 4;
// Creating the prefix array
// for the given array
cal_prefix($n, $arr);
// Queries
$queries = array(array( 1, $n, 1 ),
array( 2, $n - 2, 2 ),
array( 3, $n - 1, 3 ));
$q = count($queries);
// Perform queries
for ($i = 0; $i < $q; $i++)
echo ksub($queries[$i][0], $queries[$i][1],$n, $queries[$i][2])."\n";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
let MAX = 101;
let prefix = new Array(MAX);
for (let i = 0; i < MAX; i++) {
prefix[i] = new Array(MAX).fill(0)
}
let ar = new Array(MAX).fill(0);
// Function to calculate the prefix
function cal_prefix(n, arr) {
// Creating one based indexing
for (let i = 0; i < n; i++)
ar[i + 1] = arr[i];
// Initializing and creating prefix array
for (let i = 1; i < MAX; i++) {
for (let j = 0; j <= n; j++)
prefix[i][j] = 0;
for (let j = 1; j <= n; j++) {
// Creating a prefix array for every
// possible value in a given range
prefix[i][j] = prefix[i][j - 1]
+ (ar[j] <= i ? 1 : 0);
}
}
}
// Function to return the kth largest element
// in the index range [l, r]
function ksub(l, r, n, k) {
let lo = 1;
let hi = MAX - 1;
// Binary searching through the 2d array
// and only checking the range in which
// the sub array is a part
while (lo + 1 < hi) {
let mid = Math.floor((lo + hi) / 2);
if (prefix[mid][r] - prefix[mid][l - 1] >= k)
hi = mid;
else
lo = mid + 1;
}
if (prefix[lo][r] - prefix[lo][l - 1] >= k)
hi = lo;
return hi;
}
// Driver code
let arr = new Array(1, 4, 2, 3, 5, 7, 6);
let n = arr.length;
let k = 4;
// Creating the prefix array
// for the given array
cal_prefix(n, arr);
// Queries
let queries = new Array(new Array(1, n, 1),
new Array(2, n - 2, 2),
new Array(3, n - 1, 3));
let q = queries.length;
// Perform queries
for (let i = 0; i < q; i++)
document.write(ksub(queries[i][0], queries[i][1], n, queries[i][2]) + "<br>");
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
1 3 5
Complejidad de tiempo: O(n + q*log(MAX)), donde n es el tamaño de la array, q es la cantidad de consultas y MAX es la cantidad de filas o columnas de la array de prefijos 2D.
Complejidad espacial: O(MAX*MAX), para almacenar elementos en la array de prefijos.
Publicación traducida automáticamente
Artículo escrito por Rafiu Jaman Mollah y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA