Найдите k-й элемент в серии, порожденной заданными N диапазонами

Опубликовано: 14 Января, 2022

Даны N неперекрывающихся диапазонов L [] и R [], где каждый диапазон начинается после окончания предыдущего диапазона, то есть L [i]> R [i - 1] для всех допустимых i . Задача состоит в том, чтобы найти K- й элемент в серии, которая образуется после сортировки всех элементов во всех заданных диапазонах в порядке возрастания.

Примеры:

Input: L[] = {1, 8, 21}, R[] = {4, 10, 23}, K = 6
Output: 9
The generated series will be 1, 2, 3, 4, 8, 9, 10, 21, 22, 23
And the 6th element is 9

Input: L[] = {2, 11, 31}, R[] = {7, 15, 43}, K = 13
Output: 32

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея заключается в использовании бинарного поиска. Весь массив для хранения количества целых чисел, которые присутствуют ДО I - й индекс, теперь с помощью этого массива узнать индекс , в котором к е число будет лежать. Предположим, что индекс равен j , теперь вычислите позицию k- го наименьшего целого числа в интервале от L [j] до R [j] и найдите k- е наименьшее целое число, используя двоичный поиск, где low будет L [j], а high будет R [j] .

Below is the implementation of the above approach:

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 
Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023