د K لیستونو څخه عناصر لرونکي ترټولو کوچنۍ کچه ومومئ


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon مڼه د ګوګل über
متحرک برنامې هاش تار دوه نښې

په ستونزه کې "د K لیستونو څخه عناصر لرونکي کوچنۍ اندازه ومومئ" موږ د K لیستونه چې ترتیب شوي او ورته ورته N وړاندې کړل. دا غوښتنه کوي چې ترټولو کوچنۍ لړۍ وټاکي چې د K له هر لیست څخه لږترلږه عنصر (ونه) ولري. . که چیرې له یو څخه ډیر کوچني حد شتون ولري ، نو بیا یې هر یو حد چاپ کړئ.

بېلګه

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

وضاحت: له 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

وضاحت: له 2 څخه په 1 کېst لیست او په 6 کې 2nd لیست موږ له 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.

تشریح

موږ اک راکړ ترتیب شوی لیستونه ، د دې لپاره چې موږ باید ترټولو کوچنۍ لړۍ ومومئ او همدارنګه پدې حد کې ، لږترلږه عنصر (ونه) باید د هر لیست څخه شتون ولري. یو وکاروئ لږ من د معلوماتو جوړښت او د هغې ب characteristicsې. موږ د موجوده عنصر یا پورته عنصر په ګوته کولو لپاره ریښې یا پورتنۍ نښې ښودلې یوازې د لرې کولو یا داخلولو لپاره.

موږ به لومړی د اعظمي د ټولو لیستونو څخه عنصر ، یوځل چې موږ اعظمي عنصر وموندلو نو موږ به یې اعظمي حد ته وسپارو. نظر د 0 څخه اعظمي موندلو لپاره دیth له ټولو لیستونو څخه شاخص. فرض کړئ چې موږ درې لیستونه لرو ، اوس د ټولو لیستونو لومړی عنصر غوره کوي. موږ به دا د دوی ټولو ترمینځ پرتله کړو ، او د ټولو څخه به یې ومومو. دا یوازې د ډاډ ترلاسه کولو لپاره دی چې موږ ترټولو کوچنۍ لړۍ ترلاسه کوو. ځکه چې موږ پوهیږو موږ کولی شو له 0 څخه پیل وکړوth د ټولو لیستونو څخه شاخصونه ، مګر د کوچني کیدو لپاره د حد کمولو لپاره ، موږ به د پیل شاخص هم فشار راوړو.

اساسا ، د اعظمي عنصر موندلو وروسته ، موږ به دقیقه ګانو جوړوو. Heapify فنکشن دا زموږ لپاره هم کوي. اوس Min Heap کار کوي ځکه چې دا لومړی د لږترلږه عناصرو ذخیره کولو لپاره د صف ډول رامینځته کوي او د ډیپ رامینځته کولو له لارې په ترتیب کې زیاتوالي کې شمیره تنظیموي. نو دا فنکشن زموږ لپاره ورته کوي. مګر موږ باید ترټولو کوچنۍ لړۍ ومومو ، که څه هم موږ یو وموند. موږ باید ډاډ ترلاسه کړو چې ترټولو کوچنۍ لړۍ وي نو دا ممکن وي ، دا ، موږ کولی شو دا تازه کړو.

موږ به ارزښتونه بدل کړو ، او په ګیټ مین فعالیت کې ، موږ به زموږ کوچنی عنصر ترلاسه کړو. بیا موږ به د حد ارزښت تازه کړو. موږ باید د دې لړۍ پیل او پای ومومئ ، د پیل لږترلږه ، او پای ته باید پای ته ورسوو او هغه عنصر به چاپ کړو.

تطبیق

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]

د جاوا برنامه ترڅو د کوچني لیستونو څخه عناصر لرونکي کوچني حد ومومي

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" د هر یو اوږدوالي ده.

د ځای پیچلتیا

سمه ده) هلته "K" د لومړیتوب کتار اوږدوالی دی چې عنصر به یې ساتي.