從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個中有2個nd 列表,因此在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 分類 列表,為此我們必須找到最小的範圍,並且也在該範圍內,每個列表中至少應存在一個或多個元素編號。 用一個 最小堆 數據結構及其特徵。 我們製作了一個根指針或頂部指針,以指示當前元素或頂部元素只是要刪除或插入。

我們將首先找到 最大 所有列表中的元素,找到最大元素後,我們會將其存儲到最大值。 這個想法是從0找到最大值th 所有列表的索引。 假設我們有三個列表,現在選取所有列表的第一個元素。 我們將對它們進行比較,並找出所有的最大值。 這只是為了確保我們得到最小的範圍。 因為我們知道我們可以從0開始th 所有列表中的索引,但要減小範圍以使其成為最小索引,我們還將推送起始索引。

基本上,找出最大元素後,我們將構建一個最小堆。 堆肥 函數也為我們做到了。 現在,Min Heap完成了工作,它構建了數組類型以首先存儲最少的元素,並通過構建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) 哪裡 “ K” 是最小堆的長度, “ n” 是每個數組的長度。

空間複雜度

好) 哪裡 “ K” 是將存儲元素的優先級隊列的長度。