Рубрики

Найти наименьший диапазон, содержащий элементы из k списков

Учитывая k отсортированных списков целых чисел размером n каждый, найдите наименьший диапазон, который включает по крайней мере элемент из каждого из k списков. Если найдено более одного наименьшего диапазона, выведите любой из них.

Пример:

Input:
K = 3
arr1[] : [4, 7, 9, 12, 15]
arr2[] : [0, 8, 10, 14, 20]
arr3[] : [6, 12, 16, 30, 50]
Output:
The smallest range is [6 8] 
Explanation: Smallest range is formed by 
number 7 from first list, 8 from second
list and 6 from third list.


Input: 
k = 3
arr1[] : [4, 7]
arr2[] : [1, 2]
arr3[] : [20, 40]
The smallest range is [2 20]  

Наивный подход: идея состоит в том, чтобы поддерживать указатели на каждый список, используя массив ptr [k]. Ниже приведены шаги:

  1. Первоначально индекс каждого списка равен 0, поэтому инициализируйте каждый элемент ptr [0..k] в 0;
  2. Повторите следующие шаги, пока не исчерпан хотя бы один список:
    • Теперь найдите минимальное и максимальное значение среди текущих элементов всего списка, указанного массивом ptr [0… k].
    • Теперь обновите minrange, если ток (max-min) меньше minrange.
    • увеличить указатель, указывающий на текущий минимальный элемент.

C ++

// Программа на C ++ для определения наименьшего диапазона, который включает
// элементы из каждого из отсортированных списков.
#include <bits/stdc++.h>

  

using namespace std;

  
#define N 5

  
// массив для хранения текущего индекса списка i

int ptr[501];

  
// Эта функция принимает k отсортированных списков в виде
// 2D массив в качестве аргумента. Он обнаруживает наименьший диапазон
// это включает элементы из каждого из k списков.

void findSmallestRange(int arr[][N], int n, int k)

{

      int i,minval,maxval,minrange,minel,maxel,flag,minind;

        

      // инициализация в 0 index;

      for(i = 0;i <= k;i++) 

        ptr[i] = 0;

  

      minrange = INT_MAX;

        

      while(1)       

      {

            // для поддержки индекса списка, содержащего минимальный элемент

          minind = -1; 

          minval = INT_MAX;

          maxval = INT_MIN;

          flag = 0;

  

          // перебираем весь список

          for(i = 0;i < k;i++)   

          {    

                // если каждый элемент списка [i] пройден, то разрывать цикл

              if(ptr[i] == n)   

              {

                flag = 1;

                break;

              }

              // найти минимальное значение среди всех элементов списка, указывающих массивом ptr []

              if(ptr[i] < n && arr[i][ptr[i]] < minval)  

              {

                  minind=i;  // обновляем индекс списка

                  minval=arr[i][ptr[i]];

              }

              // найти максимальное значение среди всех элементов списка, указывающих массивом ptr []

              if(ptr[i] < n && arr[i][ptr[i]] > maxval)    

              {

                  maxval = arr[i][ptr[i]];

              }

          }

  

          // если какой-либо список исчерпан, мы не получим лучшего ответа, так что прервите цикл while

          if(flag) 

            break;

  

          ptr[minind]++;

  

          // обновляем минранж

          if((maxval-minval) < minrange)  

          {

              minel = minval;

              maxel = maxval;

              minrange = maxel - minel;

          }

      }

        

      printf("The smallest range is [%d , %d]\n",minel,maxel);

}    

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[][N] = {

                    {4, 7, 9, 12, 15},

                    {0, 8, 10, 14, 20},

                    {6, 12, 16, 30, 50}

                    };

  

    int k = sizeof(arr)/sizeof(arr[0]);

   

    findSmallestRange(arr,N,k);

   

    return 0;

}
// Этот код предоставлен Адитьей Кришной Намдео

Джава

// Java-программа для определения наименьшего диапазона, который включает
// элементы из каждого из отсортированных списков.

class GFG {

  

    static final int N = 5;

  
// массив для хранения текущего индекса списка i

    static int ptr[] = new int[501];

  
// Эта функция принимает k отсортированных списков в виде
// 2D массив в качестве аргумента. Он обнаруживает наименьший диапазон
// это включает элементы из каждого из k списков.

    static void findSmallestRange(int arr[][], int n, int k) {

        int i, minval, maxval, minrange, minel = 0, maxel = 0, flag, minind;

  

        // инициализация в 0 index;

        for (i = 0; i <= k; i++) {

            ptr[i] = 0;

        }

  

        minrange = Integer.MAX_VALUE;

  

        while (true) {

            // для поддержки индекса списка, содержащего минимальный элемент

            minind = -1;

            minval = Integer.MAX_VALUE;

            maxval = Integer.MIN_VALUE;

            flag = 0;

  

            // перебираем весь список

            for (i = 0; i < k; i++) {

                // если каждый элемент списка [i] пройден, то разрывать цикл

                if (ptr[i] == n) {

                    flag = 1;

                    break;

                }

                // найти минимальное значение среди всех элементов списка, указывающих массивом ptr []

                if (ptr[i] < n && arr[i][ptr[i]] < minval) {

                    minind = i;  // обновляем индекс списка

                    minval = arr[i][ptr[i]];

                }

                // найти максимальное значение среди всех элементов списка, указывающих массивом ptr []

                if (ptr[i] < n && arr[i][ptr[i]] > maxval) {

                    maxval = arr[i][ptr[i]];

                }

            }

  

            // если какой-либо список исчерпан, мы не получим лучшего ответа, так что прервите цикл while

            if (flag == 1) {

                break;

            }

  

            ptr[minind]++;

  

            // обновляем минранж

            if ((maxval - minval) < minrange) {

                minel = minval;

                maxel = maxval;

                minrange = maxel - minel;

            }

        }

        System.out.printf("The smallest range is [%d , %d]\n", minel, maxel);

    }

  
// Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) {

  

        int arr[][] = {

            {4, 7, 9, 12, 15},

            {0, 8, 10, 14, 20},

            {6, 12, 16, 30, 50}

        };

  

        int k = arr.length;

  

        findSmallestRange(arr, N, k);

  

    }

}
// этот код предоставлен Rajput-Ji

питон

# Python3 программа для выяснения
# наименьший диапазон, который включает
# элементы от каждого из
# даны отсортированные списки.

  

N = 5

  
# массив для хранения
# текущий индекс списка i

ptr = [0 for i in range(501)]

  
# Эта функция принимает к сортировке
# списки в виде 2D массива в виде
# Аргумент. Выясняет самое маленькое
# диапазон, который включает элементы из
# каждый из k списков.

def findSmallestRange(arr, n, k):

  

    i, minval, maxval, minrange, minel, maxel, flag, minind = 0, 0, 0, 0, 0, 0, 0, 0

          

    # инициализация до 0 индекса

    for i in range(k + 1):

        ptr[i] = 0

  

    minrange = 10**9

          

    while(1):    

          

            # для ведения индекса списка

            # содержащий минимальный элемент

        minind = -1

        minval = 10**9

        maxval = -10**9

        flag = 0

  

        # повторение по всему списку

        for i in range(k):

              

                # если каждый элемент списка [i]

                # пройдено, затем разорвать цикл

            if(ptr[i] == n):

                flag = 1    

                break

  

            # найти минимальное значение среди всего списка

            # элементы, указывающие массивом ptr []

            if(ptr[i] < n and arr[i][ptr[i]] < minval):

                minind = i # обновить индекс списка

                minval = arr[i][ptr[i]]

              

            # найти максимальное значение среди всех

            # элементы списка, указываемые массивом ptr []

            if(ptr[i] < n and arr[i][ptr[i]] > maxval):

                maxval = arr[i][ptr[i]]

              

          

  

        # если какой-либо список исчерпать мы будем

        # нет лучшего ответа,

        # так что прервите цикл

        if(flag):

            break

  

        ptr[minind] += 1

  

        # обновление минранж

        if((maxval-minval) < minrange):

            minel = minval

            maxel = maxval

            minrange = maxel - minel

      

    print("The smallest range is [", minel, maxel,"]")

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

arr= [

    [4, 7, 9, 12, 15],

    [0, 8, 10, 14, 20],

    [6, 12, 16, 30, 50]

    ]

  

k = len(arr)

  
findSmallestRange(arr, N, k)

  
# Этот код предоставлен Мохит Кумар

C #

// C # программа, чтобы узнать наименьшее
// диапазон, который включает элементы из
// каждый из указанных отсортированных списков.

using System;

  

class GFG

  

    static int N = 5; 

  

    // массив для хранения текущего индекса списка i

    static int []ptr = new int[501]; 

  

    // Эта функция принимает к сортировке

    // списки в виде 2D массива как

    // Аргумент. Он обнаруживает наименьший диапазон

    // это включает элементы из каждого из k списков.

    static void findSmallestRange(int [,]arr, 

                                int n, int k)

    

        int i, minval, maxval, minrange, 

        minel = 0, maxel = 0, flag, minind; 

  

        // инициализация в 0 index;

        for (i = 0; i <= k; i++) 

        

            ptr[i] = 0; 

        

  

        minrange = int.MaxValue; 

  

        while (true

        

            // для поддержания индекса

            // список, содержащий минимальный элемент

            minind = -1; 

            minval = int.MaxValue; 

            maxval = int.MinValue; 

            flag = 0; 

  

            // перебираем весь список

            for (i = 0; i < k; i++) 

            

                // если каждый элемент списка [i]

                // пройден, затем разорвать цикл

                if (ptr[i] == n)

                

                    flag = 1; 

                    break

                

                  

                // найти минимальное значение среди всех

                // список элементов, указывающих массивом ptr []

                if (ptr[i] < n && arr[i,ptr[i]] < minval) 

                

                    minind = i; // обновляем индекс списка

                    minval = arr[i,ptr[i]]; 

                

                  

                // найти максимальное значение среди всех

                // список элементов, указывающих массивом ptr []

                if (ptr[i] < n && arr[i,ptr[i]] > maxval)

                

                    maxval = arr[i,ptr[i]]; 

                

            

  

            // если какой-нибудь список исчерпаем

            // нет лучшего ответа,

            // так что прервите цикл while

            if (flag == 1)

            

                break

            

  

            ptr[minind]++; 

  

            // обновляем минранж

            if ((maxval - minval) < minrange) 

            

                minel = minval; 

                maxel = maxval; 

                minrange = maxel - minel; 

            

        

        Console.WriteLine("The smallest range is"

                           "[{0} , {1}]\n", minel, maxel); 

    

  

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

    public static void Main(String[] args) 

    

  

        int [,]arr = { 

            {4, 7, 9, 12, 15}, 

            {0, 8, 10, 14, 20}, 

            {6, 12, 16, 30, 50} 

        }; 

  

        int k = arr.GetLength(0); 

  

        findSmallestRange(arr, N, k); 

    

  
// Этот код предоставлен 29AjayKumar


Выход :

The smallest range is [6 8]

Временная сложность: O (n 2 k)

Более эффективный подход — использовать минимальную кучу. Ниже приведены шаги —

  1. Создайте минимальную кучу размера k и вставьте первые элементы всех k списков в кучу.
  2. Поддерживайте две переменные min и max для хранения минимальных и максимальных значений, присутствующих в куче в любой точке. Примечание min всегда будет содержать значение корня кучи.
  3. Повторите следующие шаги
    • Получить минимальный элемент из кучи (минимум всегда в корне) и вычислить диапазон.
    • Замените корень кучи следующим элементом списка, из которого извлечен элемент min. Заменив рут, поменяйте дерево. Обновите max, если следующий элемент больше. Если в списке больше нет элементов, прервите цикл.

Ниже приведена реализация вышеуказанного подхода —

C ++

// Программа на C ++ для определения наименьшего диапазона, который включает
// элементы из каждого из отсортированных списков.
#include<iostream>
#include<limits.h>

using namespace std;

  
#define N 5

  
// Узел минимальной кучи

struct MinHeapNode

{

    int element; // Элемент, который будет сохранен

    int i; // индекс списка, из которого взят элемент

    int j; // индекс следующего элемента, который будет выбран из списка

};

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

void swap(MinHeapNode *x, MinHeapNode *y);

  
// Класс для Min Heap

class MinHeap

{

    MinHeapNode *harr; // указатель на массив элементов в куче

    int heap_size; // размер кучи мин

public:

    // Конструктор: создает минимальную кучу заданного размера

    MinHeap(MinHeapNode a[], int size);

  

    // сложить поддерево с корнем по заданному индексу

    void MinHeapify(int );

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2*i + 1); }

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2*i + 2); }

  

    // чтобы получить рут

    MinHeapNode getMin() { return harr[0]; }

  

    // заменить корень новым узлом x и heapify () новым корнем

    void replaceMin(MinHeapNode x) { harr[0] = x; MinHeapify(0); }

};

  
// Конструктор: строит кучу из заданного массива a [] заданного размера

MinHeap::MinHeap(MinHeapNode a[], int size)

{

    heap_size = size;

    harr = a; // сохранить адрес массива

    int i = (heap_size - 1)/2;

    while (i >= 0)

    {

        MinHeapify(i);

        i--;

    }

}

  
// Рекурсивный метод, чтобы накапливать поддерево с корнем в
// данный индекс. Этот метод предполагает, что поддеревья
// уже куча

void MinHeap::MinHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

    if (l < heap_size &&

        harr[l].element < harr[i].element)

        smallest = l;

    if (r < heap_size &&

        harr[r].element < harr[smallest].element)

        smallest = r;

    if (smallest != i)

    {

        swap(harr[i], harr[smallest]);

        MinHeapify(smallest);

    }

}

  
// Эта функция принимает k отсортированных списков в виде
// 2D массив в качестве аргумента. Он обнаруживает наименьший диапазон
// это включает элементы из каждого из k списков.

void findSmallestRange(int arr[][N], int k)

{

    // Создать минимальную кучу с k узлами кучи. Каждый узел кучи

    // имеет первый элемент списка

    int range = INT_MAX;

    int min = INT_MAX, max = INT_MIN;

    int start, end;

  

    MinHeapNode *harr = new MinHeapNode[k];

    for (int i = 0; i < k; i++)

    {

        harr[i].element = arr[i][0]; // Сохраняем первый элемент

        harr[i].i = i; // индекс списка

        harr[i].j = 1; // Индекс следующего элемента, который будет сохранен

                       // из списка

  

        // сохраняем элемент max

        if (harr[i].element > max)

            max = harr[i].element;

    }

  

    MinHeap hp(harr, k); // Создать кучу

  

    // Теперь один за другим получаем минимальный элемент из min

    // куча и заменить его следующим элементом списка

    while (1)

    {

        // Получить минимальный элемент и сохранить его на выходе

        MinHeapNode root = hp.getMin();

  

        // обновление мин

        min = hp.getMin().element;

  

        // обновить диапазон

        if (range > max - min + 1)

        {

            range = max - min + 1;

            start = min;

            end = max;

        }

  

        // Найти следующий элемент, который заменит текущий

        // корень кучи. Следующий элемент принадлежит тому же

        // перечислить как текущий корень.

        if (root.j < N)

        {

            root.element = arr[root.i][root.j];

            root.j += 1;

  

            // обновляем элемент max

            if (root.element > max)

                max = root.element;

        }

  

        // разрыв, если мы достигли конца любого списка

        else break;

  

        // Заменить корень следующим элементом списка

        hp.replaceMin(root);

    }

  

    cout << "The smallest range is " << "["

         << start << " " << end << "]" << endl;;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[][N] = {

                    {4, 7, 9, 12, 15},

                    {0, 8, 10, 14, 20},

                    {6, 12, 16, 30, 50}

                    };

    int k = sizeof(arr)/sizeof(arr[0]);

  

    findSmallestRange(arr, k);

  

    return 0;

}

Джава

// Java-программа для поиска самых маленьких
// диапазон, который включает элементы из
// каждый из указанных отсортированных списков.

class GFG

{

  

    // Узел минимальной кучи

    static class Node 

    {

        int ele; // Элемент, который будет сохранен

        int i;     // индекс списка, из которого

                 // элемент взят

        int j;     // индекс следующего элемента

                 // быть выбранным из списка

  

        Node(int a, int b, int c)

        {

            this.ele = a;

            this.i = b;

            this.j = c;

        }

    }

  

    // Класс для Min Heap

    static class MinHeap

    {

        Node[] harr; // массив элементов в куче

        int size;     // размер кучи мин

  

        // Конструктор: создает минимальную кучу

        // заданного размера

        MinHeap(Node[] arr, int size)

        {

            this.harr = arr;

            this.size = size;

            int i = (size - 1) / 2;

            while (i >= 0

            {

                MinHeapify(i);

                i--;

            }

        }

  

        // получить индекс левого ребенка

        // узла по индексу i

        int left(int i) 

        {

            return 2 * i + 1;

        }

  

        // получить индекс нужного ребенка

        // узла по индексу i

        int right(int i) 

        {

            return 2 * i + 2;

        }

  

        // сложить поддерево с

        // корень по указанному индексу

        void MinHeapify(int i) 

        {

            int l = left(i);

            int r = right(i);

            int small = i;

            if (l < size && 

                harr[l].ele < harr[i].ele)

                small = l;

            if (r < size && 

                harr[r].ele < harr[small].ele)

                small = r;

            if (small != i) 

            {

                swap(small, i);

                MinHeapify(small);

            }

        }

  

        void swap(int i, int j)

        {

            Node temp = harr[i];

            harr[i] = harr[j];

            harr[j] = temp;

        }

  

        // чтобы получить рут

        Node getMin()

        {

            return harr[0];

        }

  

        // заменить корень новым узлом x

        // и heapify () новый корень

        void replaceMin(Node x)

        {

            harr[0] = x;

            MinHeapify(0);

        }

    }

  

    // Эта функция принимает k отсортированных списков

    // в виде двумерного массива в качестве аргумента.

    // Он находит наименьший диапазон, который включает

    // элементы из каждого из k списков.

    static void findSmallestRange(int[][] arr, int k) 

    {

        int range = Integer.MAX_VALUE;

        int min = Integer.MAX_VALUE;

        int max = Integer.MIN_VALUE;

        int start = -1, end = -1;

  

        int n = arr[0].length;

  

        // Создать минимальную кучу с k узлами кучи.

        // Каждый узел кучи имеет первый элемент списка

        Node[] arr1 = new Node[k];

        for (int i = 0; i < k; i++) 

        {

            Node node = new Node(arr[i][0], i, 1);

            arr1[i] = node;

              

            // сохраняем элемент max

            max = Math.max(max, node.ele);

        }

  

        // Создать кучу

        MinHeap mh = new MinHeap(arr1, k);

  

        // Теперь один за другим получаем минимальный элемент

        // из минимальной кучи и заменить его на

        // следующий элемент его списка

        while (true)

        {

            // Получить минимальный элемент и

            // сохранить в выходной

            Node root = mh.getMin();

  

            // обновление мин

            min = root.ele;

  

            // обновить диапазон

            if (range > max - min + 1)

            {

                range = max - min + 1;

                start = min;

                end = max;

            }

  

            // Найти следующий элемент, который будет

            // заменить текущий корень кучи.

            // Следующий элемент принадлежит тому же

            // перечислить как текущий корень.

            if (root.j < n)

            {

                root.ele = arr[root.i][root.j];

                root.j++;

  

                // обновляем элемент max

                if (root.ele > max)

                    max = root.ele;

            } else

                break;    // перерыв, если мы достигли

                        // конец любого списка

  

            // Заменить корень следующим элементом списка

            mh.replaceMin(root);

        }

        System.out.print("The smallest range is ["

                           start + " " + end + "]");

    }

  

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

    public static void main(String[] args) 

    {

        int arr[][] = {{4, 7, 9, 12, 15},

                       {0, 8, 10, 14, 20},

                       {6, 12, 16, 30, 50}};

  

        int k = arr.length;

  

        findSmallestRange(arr, k);

  

    }

}

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

C #

// C # программа, чтобы узнать наименьшее
// диапазон, который включает элементы из
// каждый из указанных отсортированных списков.

using System;

using System.Collections.Generic;

      

class GFG

{

  

    // Узел минимальной кучи

    public class Node 

    {

        public int ele;  // Элемент, который будет сохранен

        public int i;     // индекс списка, из которого

                         // элемент взят

        public int j;     // индекс следующего элемента

                         // быть выбранным из списка

  

        public Node(int a, int b, int c)

        {

            this.ele = a;

            this.i = b;

            this.j = c;

        }

    }

  

    // Класс для Min Heap

    public class MinHeap

    {

        public Node[] harr;  // массив элементов в куче

        public int size;     // размер кучи мин

  

        // Конструктор: создает минимальную кучу

        // заданного размера

        public MinHeap(Node[] arr, int size)

        {

            this.harr = arr;

            this.size = size;

            int i = (size - 1) / 2;

            while (i >= 0) 

            {

                MinHeapify(i);

                i--;

            }

        }

  

        // получить индекс левого ребенка

        // узла по индексу i

        int left(int i) 

        {

            return 2 * i + 1;

        }

  

        // получить индекс нужного ребенка

        // узла по индексу i

        int right(int i) 

        {

            return 2 * i + 2;

        }

  

        // сложить поддерево с

        // корень по указанному индексу

        void MinHeapify(int i) 

        {

            int l = left(i);

            int r = right(i);

            int small = i;

            if (l < size && 

                harr[l].ele < harr[i].ele)

                small = l;

            if (r < size && 

                harr[r].ele < harr[small].ele)

                small = r;

            if (small != i) 

            {

                swap(small, i);

                MinHeapify(small);

            }

        }

  

        void swap(int i, int j)

        {

            Node temp = harr[i];

            harr[i] = harr[j];

            harr[j] = temp;

        }

  

        // чтобы получить рут

        public Node getMin()

        {

            return harr[0];

        }

  

        // заменить корень новым узлом x

        // и heapify () новый корень

        public void replaceMin(Node x)

        {

            harr[0] = x;

            MinHeapify(0);

        }

    }

  

    // Эта функция принимает k отсортированных списков

    // в виде двумерного массива в качестве аргумента.

    // Он находит наименьший диапазон, который включает

    // элементы из каждого из k списков.

    static void findSmallestRange(int[,] arr, int k) 

    {

        int range = int.MaxValue;

        int min = int.MaxValue;

        int max = int.MinValue;

        int start = -1, end = -1;

  

        int n = arr.GetLength(0);

  

        // Создать минимальную кучу с k узлами кучи.

        // Каждый узел кучи имеет первый элемент списка

        Node[] arr1 = new Node[k];

        for (int i = 0; i < k; i++) 

        {

            Node node = new Node(arr[i, 0], i, 1);

            arr1[i] = node;

              

            // сохраняем элемент max

            max = Math.Max(max, node.ele);

        }

  

        // Создать кучу

        MinHeap mh = new MinHeap(arr1, k);

  

        // Теперь один за другим получаем минимальный элемент

        // из минимальной кучи и заменить его на

        // следующий элемент его списка

        while (true)

        {

            // Получить минимальный элемент и

            // сохранить в выходной

            Node root = mh.getMin();

  

            // обновление мин

            min = root.ele;

  

            // обновить диапазон

            if (range > max - min + 1)

            {

                range = max - min + 1;

                start = min;

                end = max;

            }

  

            // Найти следующий элемент, который будет

            // заменить текущий корень кучи.

            // Следующий элемент принадлежит тому же

            // перечислить как текущий корень.

            if (root.j < n)

            {

                root.ele = arr[root.i, root.j];

                root.j++;

  

                // обновляем элемент max

                if (root.ele > max)

                    max = root.ele;

            } else

                break// перерыв, если мы достигли

                        // конец любого списка

  

            // Заменить корень следующим элементом списка

            mh.replaceMin(root);

        }

        Console.Write("The smallest range is ["

                        start + " " + end + "]");

    }

  

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

    public static void Main(String[] args) 

    {

        int [,]arr = {{4, 7, 9, 12, 15},

                      {0, 8, 10, 14, 20},

                      {6, 12, 16, 30, 50}};

  

        int k = arr.GetLength(0);

  

        findSmallestRange(arr, k);

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход :

The smallest range is [6 8]


Сложность времени:
цикл while внутри функции findSmallestRange () может выполняться максимум n * k раз. В каждой итерации цикла мы вызываем heapify, который занимает время O (Logk). Следовательно, временная сложность составляет O (nk Logk).

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

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

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

Найти наименьший диапазон, содержащий элементы из k списков

0.00 (0%) 0 votes