k個のリストから要素を含む最小範囲を見つける


難易度 ハード
よく聞かれる Amazon (アマゾン) Apple Google ユーバー
動的計画法 ハッシュ 文字列 XNUMXつのポインター

「k個のリストから要素を含む最小範囲を見つける」という問題では、ソートされ、同じサイズNのK個のリストを指定しました。K個のリストのそれぞれから少なくとも要素を含む最小範囲を決定するように求められます。 。 最小範囲が複数存在する場合は、範囲のいずれかを印刷します。

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

説明: 2 in1からst リストと4つのうち3つrd リスト、3から2がありますnd リストなので、範囲内の2と4の範囲内で、各リストから少なくとも要素があります。

k個のリストから要素を含む最小範囲を見つける

 

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

説明: 2 in1からst リストと6in 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.

説明

私たちはakを与えました ソート リストでは、最小の範囲を見つける必要があり、その範囲内でも、各リストから少なくとも要素番号が存在する必要があります。 使う 最小ヒープ データ構造とその特性。 削除または挿入するためだけに、現在の要素またはトップ要素を示すルートまたはトップポインタを作成しました。

私たちは最初に見つけます すべてのリストから要素を見つけたら、最大の要素を見つけたら、それを最大に保存します。 アイデアは、0から最大値を見つけることですth すべてのリストからのインデックス。 0つのリストがあり、すべてのリストの最初の要素を取得するとします。 それらすべての間でそれを比較し、すべての最大値を見つけます。 これは、範囲が最小になるようにするためです。 XNUMXから始めることができることがわかっているのでth すべてのリストからインデックスを作成しますが、範囲を最小にするために、開始インデックスもプッシュします。

基本的に、最大要素を見つけた後、最小ヒープを構築します。 ヒープ化 関数は私たちのためにもそれを行います。 これで、Min Heapは、最小要素を最初に格納し、ヒープを構築することで番号を昇順で配置する配列のタイプを構築するときに作業を行います。 したがって、この関数は私たちにも同じことをします。 しかし、私たちはXNUMXつを見つけましたが、最小の範囲を見つける必要があります。 可能な限り最小の範囲であることを確認する必要があります。それにより、更新できます。

値を交換し、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) where 「K」 最小ヒープの長さと 「n」 各配列の長さです。

スペースの複雑さ

OK) where 「K」 要素を格納する優先キューの長さです。