K Тизмелерден элементтерди камтыган эң кичинекей тилкени табуу  


Кыйынчылык деңгээли катуу
Көп суралган Amazon алма Гугл Uber
Динамикалык программалоо таштанды аркан Эки көрсөткүч

“K тизмелеринен элементтерди камтыган эң кичинекей диапазонду тапкыла” маселесинде, биз иргелип, бирдей көлөмдөгү N тизмелерди бердик, ал ар бир K тизмелеринен жок дегенде элемент (тер) камтылган эң кичинекей диапазонду аныктоону өтүнөт. . Эгерде бир нече кичинекей диапазон бар болсо, анда ар кандай диапазонду басып чыгарыңыз.

мисал  

arr[][] = { {1, 2, 5, 7  }, {0, 3, 8, 9  }, {4, 6, 12,20 } }
2 4

Explanation: 2ден 1ге чейинst тизмеси жана 4 ичинде 3rd тизме, бизде 3ден 2 барnd тизме, андыктан 2 жана 4 аралыгында, ар бир тизмеден жок дегенде элементтерибиз бар.

K тизмелеринен элементтер камтылган эң кичинекей диапазонду табыңызтөөнөч

 

arr[][] = { {2, 8, 9, 20}, {6, 7, 10, 11}, {3, 14, 30, 39} };
2 6

Explanation: 2ден 1ге чейинst тизме жана 6дан 2ге чейинnd тизме бизде 3төн 3кө чейинrd тизме, андыктан 2 жана 6 аралыгында, бизде ар бир тизмеден жок дегенде элемент бар.

K тизмелеринен элементтерди камтыган эң кичинекей диапазонду табуу алгоритми  

1. Create a Heap( Min Heap Data Structure).
2. Store k elements into it picking one from each array.
3. Declare a variable min and a range and set to a maximum value of an Integer and a variable max to the maximum value of an Integer.
4. Keep storing each element from every list and find the maximum value and store it into a max variable we declared.
5. Using a root variable or any object of a Min Heap, start to find the minimum element and store it to min.
6. Find the minimum range by checking if the current (maximum − minimum ) is less than the min, range and update the range.
7. Remove the current root element or top from the used data structure and pick the next element  and insert it, from the list
8. The list that contains the minimum element, chose that.
9. Find the max element and update it according to the new element that was inserted.

түшүндүрүү  

Биз берген ак сорттолгон тизмелер, бул үчүн биз эң кичинекей диапазонду табышыбыз керек, ошондой эле ар бир тизмеде жок дегенде элементтин (с) номери болушу керек. Колдонуу Min Heap маалыматтардын структурасы жана анын мүнөздөмөлөрү. Учурдагы элементти же үстүңкү элементти алып салуу же киргизүү үчүн гана көрсөтүү үчүн тамыр же жогорку көрсөткүч жасадык.

ошондой эле
Single Number

Алгач биз табабыз эң жогорку Бардык тизмелердеги элемент, максималдуу элементти тапкандан кийин, аны максимумга чейин сактайбыз. Идеясы 0 дан максимумду табууth бардык тизмелерден индекс. Бизде үч тизме бар дейли, эми бардык тизмелердин биринчи элементин тандап жатасыз. Биз муну алардын бардыгынын ортосунда салыштырып көрүп, баарынын максимумун аныктайбыз. Бул биз эң кичинекей диапазонду алышыбыз үчүн гана керек. Себеби биз 0дон баштай аларыбызды билебизth бардык тизмелердеги индекстер, бирок диапазонду эң кичинекей кылып кыскартуу үчүн, биз баштапкы индексти түрттүрөбүз.

Негизинен, максималдуу элементти тапкандан кийин, мин үймөктү курабыз. Heapify функциясы муну биз үчүн дагы жасайт. Эми Min Heap бул ишти жасайт, анткени ал минималдуу элементтерди сактоо үчүн массивдин түрүн курат жана үймөктү куруу аркылуу санын көбөйтүү иретинде жайгаштырат. Демек, бул функция биз үчүн дагы ушундай кылат. Бирок биз эң кичине диапазонду табышыбыз керек, бирок биз аны таптык. Биз эң кичинекей диапазон болушубуз керек, андыктан аны жаңырта алабыз.

Биз баалуулуктарды алмаштырып, getMin функциясында эң кичинекей элементибизди алабыз. Андан кийин биз диапазондун маанисин жаңыртабыз. Биз ошол диапазондун башталышын жана аягын табышыбыз керек, баштоо үчүн минимум, аягына чейин жана ошол элементти басып чыгаруу үчүн.

ошондой эле
N сандарынын көбөйтүлүшүнүн минималдуу суммасы

ишке ашыруу  

K тизмелеринен элементтерди камтыган эң кичинекей диапазонду табуу үчүн C ++ программасы

#include<bits/stdc++.h>
using namespace std;
#define N 5

struct Node
{
    int element;

    int i;

    int j;
};
void swap(Node* x, Node* y);

class MinHeap
{

    Node* heapArray;

    int heap_size;

public:
    MinHeap(Node a[], int size);

    void MinHeapify(int);

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

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

    Node getMin()
    {
        return heapArray[0];
    }

    void replaceMin(Node x)
    {
        heapArray[0] = x;
        MinHeapify(0);
    }
};
MinHeap::MinHeap(Node a[], int size)
{
    heap_size = size;
    heapArray = a;
    int index = (heap_size - 1) / 2;
    while (index >= 0)
    {
        MinHeapify(index);
        index--;
    }
}
void MinHeap::MinHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && heapArray[l].element < heapArray[i].element)
        smallest = l;
    if (r < heap_size && heapArray[r].element < heapArray[smallest].element)
        smallest = r;
    if (smallest != i)
    {
        swap(heapArray[i], heapArray[smallest]);
        MinHeapify(smallest);
    }
}
void getSmallestRangeKElements(int arr[][N], int k)
{
    int range = INT_MAX;
    int min = INT_MAX, max = INT_MIN;
    int start, end;

    Node* heapArray = new Node[k];
    for (int i = 0; i < k; i++)
    {
        heapArray[i].element = arr[i][0];

        heapArray[i].i = i;

        heapArray[i].j = 1;

        if (heapArray[i].element > max)
            max = heapArray[i].element;
    }

    MinHeap MinHeapObj(heapArray, k);
    while (1)
    {
        Node root = MinHeapObj.getMin();

        min = MinHeapObj.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;

            if (root.element > max)
                max = root.element;
        }
        else
            break;

        MinHeapObj.replaceMin(root);
    }
    cout << "Smallest range: "<< "["<< start << " " << end << "]";
}
int main()
{
    int arr[][N] = {{1, 2, 5, 7  },
        {0, 3, 8, 9  },
        {4, 6, 12,20 }
    };

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

    getSmallestRangeKElements(arr, k);

    return 0;
}
Smallest range: [2 4]

K тизмелеринен элементтерди камтыган эң кичинекей диапазонду табуу үчүн Java программасы

class smallestRange
{
    public static class Node
    {
        int element;
        int i;
        int j;
        Node(int a, int b, int c)
        {
            this.element = a;
            this.i = b;
            this.j = c;
        }
    }
    public static class MinHeap
    {
        Node[] heapArray;
        int size;

        MinHeap(Node[] arr, int size)
        {
            this.heapArray = arr;
            this.size = size;
            int i = (size - 1) / 2;
            while (i >= 0)
            {
                MinHeapify(i);
                i--;
            }
        }
        int left(int i)
        {
            return 2 * i + 1;
        }
        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 && heapArray[l].element < heapArray[i].element)
                small = l;
            if (r < size && heapArray[r].element < heapArray[small].element)
                small = r;
            if (small != i)
            {
                swap(small, i);
                MinHeapify(small);
            }
        }
        void swap(int i, int j)
        {
            Node temp = heapArray[i];
            heapArray[i] = heapArray[j];
            heapArray[j] = temp;
        }
        Node getMinimum()
        {
            return heapArray[0];
        }
        void replaceMin(Node x)
        {
            heapArray[0] = x;
            MinHeapify(0);
        }
    }
    public static void getSmallestRangeKElements(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;

        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 = Math.max(max, node.element);
        }
        MinHeap MinHeapObj = new MinHeap(arr1, k);

        while (true)
        {
            Node root = MinHeapObj.getMinimum();
            min = root.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++;

                if (root.element > max)
                    max = root.element;
            }
            else
                break;

            MinHeapObj.replaceMin(root);
        }
        System.out.println("Smallest range: [" + start + " " + end + "]");
    }
    public static void main(String[] args)
    {
        int arr[][] = { {1, 2, 5, 7  },
            {0, 3, 8, 9  },
            {4, 6, 12,20 }
        };

        int k = arr.length;

        getSmallestRangeKElements(arr, k);
    }
}
Smallest range: [2 4]

Комплекстик анализ  

Убакыт татаалдыгы

O (n * k * log k) кайда "K" мин-үймөнүн узундугу жана "N" ар бир массивдин узундугу.

ошондой эле
Берилген диапазондогу элементтерден тышкары массивдин бардык сандарынын GCD сурамдары

Космостун татаалдыгы

O (k) кайда "K" элементтерди сактай турган артыкчылыктуу кезектин узундугу.