ابحث عن أصغر نطاق يحتوي على عناصر من قوائم k


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون أجهزة آبل جوجل اوبر
البرمجة الديناميكية مزيج خيط مؤشر اثنين

في المشكلة "اعثر على أصغر نطاق يحتوي على عناصر من قوائم k" ، قدمنا ​​قوائم K مرتبة وبنفس الحجم N. ويطلب تحديد النطاق الأصغر الذي يحتوي على الأقل على عنصر (عناصر) من كل قائمة من قوائم K . إذا كان هناك أكثر من نطاق أصغر ، فقم بطباعة أي نطاق.

مثال

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

التفسير: من 2 في 1st قائمة و 4 في 3rd القائمة ، لدينا 3 من 2nd قائمة ، لذلك ضمن النطاق 2 و 4 ، لدينا عناصر على الأقل من كل قائمة.

ابحث عن أصغر نطاق يحتوي على عناصر من قوائم k

 

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

التفسير: من 2 في 1st قائمة و 6 في 2nd قائمة لدينا 3 من 3rd القائمة ، لذلك ضمن النطاق 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.

تفسير

لقد قدمنا ​​ak فرز القوائم ، لذلك يتعين علينا العثور على أصغر نطاق وأيضًا ضمن هذا النطاق ، يجب أن يكون رقم العنصر (العناصر) على الأقل موجودًا من كل قائمة. إستخدم كومة دقيقة هيكل البيانات وخصائصها. لقد صنعنا مؤشرًا جذرًا أو أعلى للإشارة إلى العنصر الحالي أو العنصر العلوي لمجرد إزالته أو إدراجه.

سنجد أولا أقصى عنصر من جميع القوائم ، بمجرد العثور على الحد الأقصى للعنصر ، سنخزنه إلى الحد الأقصى. الفكرة هي إيجاد الحد الأقصى من الصفرth الفهرس من جميع القوائم. لنفترض أن لدينا ثلاث قوائم ، نلتقط الآن العنصر الأول من كل القوائم. سنقارن بينها جميعًا ، ونكتشف الحد الأقصى للجميع. هذا فقط للتأكد من أننا نحصل على أصغر نطاق. لأننا نعلم أنه يمكننا البدء من الصفرth الفهارس من جميع القوائم ، ولكن لتقليل النطاق ليصبح أصغر ، سنقوم أيضًا بدفع مؤشر البداية.

في الأساس ، بعد معرفة الحد الأقصى للعنصر ، سنقوم ببناء كومة دقيقة. كومة وظيفة تفعل ذلك لنا أيضًا. الآن يقوم Min Heap بالعمل لأنه يبني نوع المصفوفة لتخزين الحد الأدنى من العناصر أولاً وترتيب الرقم بترتيب متزايد من خلال بناء كومة. إذن هذه الوظيفة تفعل الشيء نفسه بالنسبة لنا. لكن علينا إيجاد النطاق الأصغر ، على الرغم من أننا وجدنا واحدًا. يجب أن نتأكد من أن نكون أصغر نطاق حتى يكون ممكنًا ، ويمكننا تحديثه.

سنقوم بتبادل القيم ، وفي دالة getMin ، سنحصل على أصغر عنصر لدينا. ثم سنقوم بتحديث قيمة النطاق. علينا أن نجد بداية ونهاية هذا النطاق ، الحد الأدنى للبدء ، والحد الأقصى للنهاية وسوف نقوم بطباعة هذا العنصر.

تطبيق

برنامج C ++ للعثور على أصغر نطاق يحتوي على عناصر من قوائم k

#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]

برنامج Java للعثور على أصغر نطاق يحتوي على عناصر من قوائم k

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) أين "ك" هو طول min-heap و "ن" هو طول كل مجموعة.

تعقيد الفضاء

حسنا) أين "ك" هو طول قائمة انتظار الأولوية التي ستخزن العناصر.