k 목록에서 요소를 포함하는 최소 범위 찾기


난이도 하드
자주 묻는 질문 아마존 Apple 구글 동네 짱
동적 프로그래밍 해시 두 포인터

"k 목록에서 요소를 포함하는 가장 작은 범위 찾기"문제에서 정렬되고 크기가 N 인 K 목록을 제공했습니다. 각 K 목록에서 최소한 요소를 포함하는 가장 작은 범위를 결정하도록 요청합니다. . 가장 작은 범위가 둘 이상있는 경우 범위를 인쇄합니다.

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

설명 : 2 in 1에서st 목록 및 4에서 3rd 목록, 우리는 3에서 2nd 목록이므로 범위 내 2와 4 내에는 각 목록의 요소가 적어도 있습니다.

k 개 목록의 요소를 포함하는 가장 작은 범위 찾기

 

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

설명 : 2 in 1에서st 목록 및 6 in 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에서 시작할 수 있다는 것을 알고 있기 때문에th 모든 목록에서 인덱스를 가져 오지만 범위를 가장 작게 줄이기 위해 시작 인덱스도 푸시합니다.

기본적으로 최대 요소를 찾은 후 최소 힙을 빌드합니다. 힙화 함수는 우리에게도 그렇게합니다. 이제 Min Heap은 최소 요소를 먼저 저장하는 배열 유형을 구축하고 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) 어디에 "케이" 최소 힙의 길이이며 "엔" 각 배열의 길이입니다.

공간 복잡성

확인) 어디에 "케이" 요소를 저장할 우선 순위 큐의 길이입니다.