Рубрики

Максимальное число встречаемых в n диапазонах

При заданных n диапазонах в форме L и R задача состоит в том, чтобы найти максимальное найденное целое число во всех диапазонах. Если существует более одного такого целого числа, выведите наименьшее.
0 <= L i , R i <1000000.

Примеры :

Input : L1 = 1 R1 = 15
        L2 = 4 R2 = 8
        L3 = 3 R3 = 5
        L3 = 1 R3 = 4
Output : 4

Input : L1 = 1 R1 = 15
        L2 = 5 R2 = 8
        L3 = 9 R3 = 12
        L4 = 13 R4 = 20
        L5 = 21 R5 = 30
Output : 5
Numbers having maximum occurrence i.e 2  are 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15. The smallest number
among all are 5.

Простым решением является использование хеш-таблицы для хранения количества всех чисел. Мы пересекаем каждый интервал от L i до R i и увеличиваем количество всех чисел, присутствующих в каждом интервале. Наконец, мы переходим к хеш-таблице, чтобы найти число с максимальным количеством. Временная сложность этого решения составляет O (n * MAX_INTERVAL), где MAX_INTERVAL — максимальное количество элементов в интервале.

Эффективное решение требует линейного времени. Мы создаем массив arr [] размером 1000000 (ограничение дано по максимальному значению интервала). Идея состоит в том, чтобы добавить +1 к каждому индексу L i и -1 к соответствующему индексу R i в arr []. После этого найдите префиксную сумму массива. Добавление +1 в L i показывает начальную точку i-го диапазона, а добавление -1 показывает конечную точку i-го диапазона. Наконец мы возвращаем индекс массива с максимальной суммой префикса

Алгоритм решения проблемы:

  1. Инициализируйте массив arr [] в 0.
  2. Для каждого диапазона i добавьте +1 при индексе L i и -1 при R i массива.
  3. Найдите префиксную сумму массива и найдите наименьший индекс, имеющий максимальную префиксную сумму.

Ниже приведена реализация этого подхода:

C ++

// программа на C ++ для поиска максимального числа найденных элементов в
// дано N диапазонов.
#include <bits/stdc++.h>
#define MAX 1000000

using namespace std;

  
// Возвращаем максимальное количество элементов во всех диапазонах.

int maximumOccurredElement(int L[], int R[], int n)

{

    // Инициализация всего элемента массива до 0.

    int arr[MAX];

    memset(arr, 0, sizeof arr);

  

    // Добавляем +1 по индексу Li и вычитаем 1

    // по индексу Ri.

    int maxi=-1;

    for (int i = 0; i < n; i++) {

        arr[L[i]] += 1;

        arr[R[i] + 1] -= 1;

        if(R[i]>maxi){

            maxi=R[i];

        }

    }

  

    // Находим префиксную сумму и индекс, имеющий максимум

    // префикс суммы.

    int msum = arr[0],ind;

    for (int i = 1; i < maxi+1; i++) {

        arr[i] += arr[i - 1];

        if (msum < arr[i]) {

            msum = arr[i];

            ind = i;

        }

    }

  

    return ind;

}

  
// Управляемая программа

int main()

{

    int L[] = { 1, 4, 9, 13, 21 };

    int R[] = { 15, 8, 12, 20, 30 };

    int n = sizeof(L) / sizeof(L[0]);

  

    cout << maximumOccurredElement(L, R, n) << endl;

    return 0;

}

Джава

// Java-программа для поиска максимума произошла
// элемент в заданных N диапазонах.

import java.io.*;

  

class GFG {

  

    static int MAX = 1000000;

  

    // Возвращаем максимальное количество элементов во всех диапазонах.

    static int maximumOccurredElement(int[] L, int[] R, int n)

    {

        // Инициализация всего элемента массива до 0.

        int[] arr = new int[MAX];

  

        // Добавляем +1 по индексу Li и

        // вычитаем 1 по индексу Ri.

        int maxi=-1;

        for (int i = 0; i < n; i++) {

            arr[L[i]] += 1;

            arr[R[i] + 1] -= 1;

            if(R[i]>maxi){

            maxi=R[i];

           }

        }

  

        // Нахождение префикса sum и index

        // с максимальной суммой префикса.

        int msum = arr[0];

        int ind = 0;

        for (int i = 1; i < maxi+1; i++) {

            arr[i] += arr[i - 1];

            if (msum < arr[i]) {

                msum = arr[i];

                ind = i;

            }

        }

  

        return ind;

    }

  

    // Драйвер программы

    static public void main(String[] args)

    {

        int[] L = { 1, 4, 9, 13, 21 };

        int[] R = { 15, 8, 12, 20, 30 };

        int n = L.length;

        System.out.println(maximumOccurredElement(L, R, n));

    }

}

  
// Этот код предоставлен vt_m.

python3

# Программа Python 3, чтобы найти максимум произошедшего
# элемент в заданных N диапазонах.

  

MAX = 1000000

  
# Возврат максимального произошедшего элемента
# во всех диапазонах.

def maximumOccurredElement(L, R, n):

      

    # Инициализация всего элемента массива до 0.

    arr = [0 for i in range(MAX)]

  

    # Добавление +1 в индексе Li и вычитание 1

    # по индексу Ri.

    for i in range(0, n, 1):

        arr[L[i]] += 1

        arr[R[i] + 1] -= 1

  

    # Нахождение префикса сумма и индекс

    # с максимальной суммой префикса.

    msum = arr[0]

    for i in range(1, MAX, 1):

        arr[i] += arr[i - 1]

        if (msum < arr[i]):

            msum = arr[i]

            ind = i

    return ind

  
Код водителя

if __name__ == '__main__':

    L = [1, 4, 9, 13, 21]

    R = [15, 8, 12, 20, 30]

    n = len(L)

  

    print(maximumOccurredElement(L, R, n))

      
# Этот код предоставлен
# Sanjit_Prasad

C #

// C # программа для поиска максимума
// возник элемент в заданных N диапазонах.

using System;

  

class GFG {

  

    static int MAX = 1000000;

  

    // Возвращаем максимальное количество элементов во всех диапазонах.

    static int maximumOccurredElement(int[] L, int[] R, int n)

    {

        // Инициализация всего элемента массива до 0.

        int[] arr = new int[MAX];

  

        // Добавляем +1 по индексу Li и

        // вычитаем 1 по индексу Ri.

        for (int i = 0; i < n; i++) {

            arr[L[i]] += 1;

            arr[R[i] + 1] -= 1;

        }

  

        // Нахождение префикса sum и index

        // с максимальной суммой префикса.

        int msum = arr[0];

        int ind = 0;

        for (int i = 1; i < MAX; i++) {

            arr[i] += arr[i - 1];

            if (msum < arr[i]) {

                msum = arr[i];

                ind = i;

            }

        }

  

        return ind;

    }

  

    // Драйвер программы

    static public void Main()

    {

        int[] L = { 1, 4, 9, 13, 21 };

        int[] R = { 15, 8, 12, 20, 30 };

        int n = L.Length;

        Console.WriteLine(maximumOccurredElement(L, R, n));

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа, чтобы найти максимум произошедшего
// элемент в заданных N диапазонах.

$MAX = 1000000;

  
// Возвращаем максимальное количество элементов
// во всех диапазонах.

function maximumOccurredElement($L, $R, $n)

{

  

    // Инициализация всего элемента

    // массива до 0.

    $arr = array();

    for($i = 0; $i < $n; $i++)

    {

        $arr[] = "0";

    }

  

    // Добавляем +1 по индексу Li и вычитаем 1

    // по индексу Ri.

    for ($i = 0; $i < $n; $i++) 

    {

        $arr[$L[$i]] += 1;

        $arr[$R[$i] + 1] -= 1;

    }

      

    // Нахождение префикса sum и index

    // с максимальной суммой префикса.

    $msum = $arr[0];

      

    for ($i = 1; $i <$n; $i++) 

    {

        $arr[$i] += $arr[$i - 1];

        if ($msum < $arr[$i])

        {

            $msum = $arr[$i];

            $ind = $i;

        }

    }

    return $ind;

}

  
// Код драйвера

$L = array(1, 4, 9, 13, 21);

$R = array(15, 8, 12, 20, 30);

$n = count($L);

  

echo maximumOccurredElement($L, $R, $n);

  
// Этот код предоставлен
// Srathore
?>


Выход:

4

Сложность времени: O (n + MAX)

Упражнение: Попробуйте для 0 <= L i , R i <= 1000000000. (Подсказка: используйте карту stl).

Связанная статья: Максимальное значение в массиве после m операций увеличения диапазона

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Максимальное число встречаемых в n диапазонах

0.00 (0%) 0 votes