K тізімдерінен ең кіші элементтерді табыңыз


Күрделілік дәрежесі қиын
Жиі кіреді Amazon алма Google қиятын
Динамикалық бағдарламалау Hash String Екі көрсеткіш

«K тізімдерінен элементтері бар ең кіші диапазонды табыңыз» деген есепте біз сұрыпталған және бірдей N өлшемдегі K тізімдерін бердік, ол әр 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.

Түсіндіру

Біз ак сұрыпталған тізімдер, бұл үшін біз ең кіші диапазонды табуға тиіспіз, сонымен қатар әр тізімде кем дегенде элемент (тер) нөмірі болуы керек. А Мин үйме мәліметтер құрылымы және оның сипаттамалары. Ағымдағы элементті немесе жоғарғы элементті тек алып тастау немесе кірістіру үшін көрсету үшін түбір немесе жоғарғы көрсеткіш жасадық.

Алдымен біз оны табамыз максимум барлық тізімдердегі элемент, максималды элементті тапқаннан кейін оны максимумға дейін сақтаймыз. Идеясы - 0-ден максимумды табуth барлық тізімдердің индексі. Бізде үш тізім бар делік, енді барлық тізімдердің бірінші элементін таңдап алыңыз. Біз оны бәрінің арасында салыстырып, барлығының максимумын анықтаймыз. Бұл біздің ең кіші диапазонға ие екендігіміз үшін ғана. Біз 0-ден бастауға болатындығын білемізth барлық тізімдердің индекстері, бірақ ең кіші болу үшін диапазонды азайту үшін біз де бастапқы индекске итермелейтін боламыз.

Негізінде, максималды элементті анықтағаннан кейін біз мин үйіндісін саламыз. Heapify функциясы мұны біз үшін де жасайды. Енді Min Heap жұмысты минималды элементтерді сақтау үшін массив типін құра отырып және үйінді құру арқылы санды өсу ретімен реттейді. Сондықтан бұл функция біз үшін де солай етеді. Бірақ біз ең кішкентай диапазонды табуымыз керек, дегенмен біз оны таптық. Біз оны ең кіші диапазонға айналдыруымыз керек, мүмкін оны жаңарта аламыз.

Біз мәндерді ауыстырамыз, ал getMin функциясында біз ең кіші элементті аламыз. Сонда біз диапазон мәнін жаңартамыз. Біз бұл диапазонның басы мен соңын, ең азын және ең үлкенін және соңын табуымыз керек және сол элементті басып шығарамыз.

Іске асыру

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» әр массивтің ұзындығы.

Ғарыштың күрделілігі

Жарайды ма) қайда «K» - бұл элементтерді сақтайтын кезектің ұзақтығы.