Dados N rangos no superpuestos L[] y R[] donde cada rango comienza después de que finaliza el rango anterior, es decir , L[i] > R[i – 1] para todos los i válidos . La tarea es encontrar el K -ésimo elemento en la serie que se forma después de ordenar todos los elementos en todos los rangos dados en orden ascendente.
Ejemplos:
Entrada: L[] = {1, 8, 21}, R[] = {4, 10, 23}, K = 6
Salida: 9
La serie generada será 1, 2, 3, 4, 8, 9, 10 , 21, 22, 23
Y el sexto elemento es 9
Entrada: L[] = {2, 11, 31}, R[] = {7, 15, 43}, K = 13
Salida: 32
Enfoque: La idea es utilizar la búsqueda binaria . Una array total para almacenar el número de enteros que están presentes hasta el i -ésimo índice, ahora con la ayuda de esta array, descubra el índice en el que se encontrará el k -ésimo entero. Suponga que el índice es j , ahora calcule la posición del k -ésimo entero más pequeño en el intervalo L[j] a R[j] y encuentre el k -ésimo entero más pequeño usando la búsqueda binaria donde bajo será L[j] y alto será R[j] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the kth element
// of the required series
int getKthElement(int n, int k, int L[], int R[])
{
int l = 1;
int h = n;
// To store the number of integers that lie
// upto the ith index
int total[n + 1];
total[0] = 0;
// Compute the number of integers
for (int i = 0; i < n; i++) {
total[i + 1] = total[i] + (R[i] - L[i]) + 1;
}
// Stores the index, lying from 1
// to n,
int index = -1;
// Using binary search, find the index
// in which the kth element will lie
while (l <= h) {
int m = (l + h) / 2;
if (total[m] > k) {
index = m;
h = m - 1;
}
else if (total[m] < k)
l = m + 1;
else {
index = m;
break;
}
}
l = L[index - 1];
h = R[index - 1];
// Find the position of the kth element
// in the interval in which it lies
int x = k - total[index - 1];
while (l <= h) {
int m = (l + h) / 2;
if ((m - L[index - 1]) + 1 == x) {
return m;
}
else if ((m - L[index - 1]) + 1 > x)
h = m - 1;
else
l = m + 1;
}
}
// Driver code
int main()
{
int L[] = { 1, 8, 21 };
int R[] = { 4, 10, 23 };
int n = sizeof(L) / sizeof(int);
int k = 6;
cout << getKthElement(n, k, L, R);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the kth element
// of the required series
static int getKthElement(int n, int k,
int L[], int R[])
{
int l = 1;
int h = n;
// To store the number of integers that lie
// upto the ith index
int total[] = new int[n + 1];
total[0] = 0;
// Compute the number of integers
for (int i = 0; i < n; i++)
{
total[i + 1] = total[i] +
(R[i] - L[i]) + 1;
}
// Stores the index, lying from 1
// to n,
int index = -1;
// Using binary search, find the index
// in which the kth element will lie
while (l <= h)
{
int m = (l + h) / 2;
if (total[m] > k)
{
index = m;
h = m - 1;
}
else if (total[m] < k)
l = m + 1;
else
{
index = m;
break;
}
}
l = L[index - 1];
h = R[index - 1];
// Find the position of the kth element
// in the interval in which it lies
int x = k - total[index - 1];
while (l <= h)
{
int m = (l + h) / 2;
if ((m - L[index - 1]) + 1 == x)
{
return m;
}
else if ((m - L[index - 1]) + 1 > x)
h = m - 1;
else
l = m + 1;
}
return k;
}
// Driver code
public static void main(String[] args)
{
int L[] = { 1, 8, 21 };
int R[] = { 4, 10, 23 };
int n = L.length;
int k = 6;
System.out.println(getKthElement(n, k, L, R));
}
}
// This code is contributed by Code_Mech
Python3
# Python3 implementation of the approach # Function to return the kth element # of the required series def getKthElement(n, k, L, R): l = 1 h = n # To store the number of integers that lie # upto the ith index total=[0 for i in range(n + 1)] total[0] = 0 # Compute the number of integers for i in range(n): total[i + 1] = total[i] + (R[i] - L[i]) + 1 # Stores the index, lying from 1 # to n, index = -1 # Using binary search, find the index # in which the kth element will lie while (l <= h): m = (l + h) // 2 if (total[m] > k): index = m h = m - 1 elif (total[m] < k): l = m + 1 else : index = m break l = L[index - 1] h = R[index - 1] # Find the position of the kth element # in the interval in which it lies x = k - total[index - 1] while (l <= h): m = (l + h) // 2 if ((m - L[index - 1]) + 1 == x): return m elif ((m - L[index - 1]) + 1 > x): h = m - 1 else: l = m + 1 # Driver code L=[ 1, 8, 21] R=[4, 10, 23] n = len(L) k = 6 print(getKthElement(n, k, L, R)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the kth element
// of the required series
static int getKthElement(int n, int k,
int[] L, int[] R)
{
int l = 1;
int h = n;
// To store the number of integers that lie
// upto the ith index
int[] total = new int[n + 1];
total[0] = 0;
// Compute the number of integers
for (int i = 0; i < n; i++)
{
total[i + 1] = total[i] +
(R[i] - L[i]) + 1;
}
// Stores the index, lying from 1
// to n,
int index = -1;
// Using binary search, find the index
// in which the kth element will lie
while (l <= h)
{
int m = (l + h) / 2;
if (total[m] > k)
{
index = m;
h = m - 1;
}
else if (total[m] < k)
l = m + 1;
else
{
index = m;
break;
}
}
l = L[index - 1];
h = R[index - 1];
// Find the position of the kth element
// in the interval in which it lies
int x = k - total[index - 1];
while (l <= h)
{
int m = (l + h) / 2;
if ((m - L[index - 1]) + 1 == x)
{
return m;
}
else if ((m - L[index - 1]) + 1 > x)
h = m - 1;
else
l = m + 1;
}
return k;
}
// Driver code
public static void Main()
{
int[] L = { 1, 8, 21 };
int[] R = { 4, 10, 23 };
int n = L.Length;
int k = 6;
Console.WriteLine(getKthElement(n, k, L, R));
}
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP implementation of the approach
// Function to return the kth element
// of the required series
function getKthElement($n, $k, $L, $R)
{
$l = 1;
$h = $n;
// To store the number of integers that lie
// upto the ith index
$total = array();
$total[0] = 0;
// Compute the number of integers
for ($i = 0; $i < $n; $i++)
{
$total[$i + 1] = $total[$i] +
($R[$i] - $L[$i]) + 1;
}
// Stores the index, lying from 1
// to n,
$index = -1;
// Using binary search, find the index
// in which the kth element will lie
while ($l <= $h)
{
$m = floor(($l + $h) / 2);
if ($total[$m] > $k)
{
$index = $m;
$h = $m - 1;
}
else if ($total[$m] < $k)
$l = $m + 1;
else
{
$index = $m;
break;
}
}
$l = $L[$index - 1];
$h = $R[$index - 1];
// Find the position of the kth element
// in the interval in which it lies
$x = $k - $total[$index - 1];
while ($l <= $h)
{
$m = floor(($l + $h) / 2);
if (($m - $L[$index - 1]) + 1 == $x)
{
return $m;
}
else if (($m - $L[$index - 1]) + 1 > $x)
$h = $m - 1;
else
$l = $m + 1;
}
}
// Driver code
$L = array( 1, 8, 21 );
$R = array( 4, 10, 23 );
$n = count($L);
$k = 6;
echo getKthElement($n, $k, $L, $R);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the kth element
// of the required series
function getKthElement(n,k,L,R)
{
let l = 1;
let h = n;
// To store the number of integers that lie
// upto the ith index
let total = new Array(n + 1);
total[0] = 0;
// Compute the number of integers
for (let i = 0; i < n; i++)
{
total[i + 1] = total[i] +
(R[i] - L[i]) + 1;
}
// Stores the index, lying from 1
// to n,
let index = -1;
// Using binary search, find the index
// in which the kth element will lie
while (l <= h)
{
let m = Math.floor((l + h) / 2);
if (total[m] > k)
{
index = m;
h = m - 1;
}
else if (total[m] < k)
l = m + 1;
else
{
index = m;
break;
}
}
l = L[index - 1];
h = R[index - 1];
// Find the position of the kth element
// in the interval in which it lies
let x = k - total[index - 1];
while (l <= h)
{
let m = Math.floor((l + h) / 2);
if ((m - L[index - 1]) + 1 == x)
{
return m;
}
else if ((m - L[index - 1]) + 1 > x)
h = m - 1;
else
l = m + 1;
}
return k;
}
// Driver code
let L = [1, 8, 21 ];
let R = [ 4, 10, 23 ];
let n = L.length;
let k = 6;
document.write(getKthElement(n, k, L, R));
// This code is contributed by patel2127
</script>
Producción:
9
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA