រកឃើញជួរតូចបំផុតដែលមានផ្ទុកធាតុពី k បញ្ជី


កម្រិតលំបាក រឹង
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ក្រុមហ៊ុន google Uber
ការសរសេរកម្មវិធីឌីណាមិក ហាស់ ខ្សែអក្សរ ទ្រនិចពីរ

ក្នុងបញ្ហា "រកជួរតូចបំផុតដែលផ្ទុកធាតុពីបញ្ជី K" យើងបានផ្តល់បញ្ជី K ដែលត្រូវបានតម្រៀបនិងមានទំហំ N។ វាស្នើឱ្យកំណត់ជួរតូចបំផុតដែលមានធាតុយ៉ាងហោចណាស់ពីបញ្ជី K នីមួយៗ។ ។ ប្រសិនបើមានជួរតូចបំផុតច្រើនជាងមួយ, បន្ទាប់មកបោះពុម្ពជួរណាមួយ។

ឧទាហរណ៍

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

ការពន្យល់: ពី 2 ក្នុង 1st បញ្ជីនិង ៤ ក្នុង ៣rd បញ្ជី, យើងមាន 3 ពី 2nd បញ្ជីដូច្នេះនៅក្នុងជួរទី ២ និងទី ៤ យើងមានយ៉ាងហោចណាស់ធាតុពីបញ្ជីនីមួយៗ។

រកជួរតូចបំផុតដែលមានធាតុពីបញ្ជី k

 

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

ការពន្យល់: ពី 2 ក្នុង 1st បញ្ជីនិង ៦ ក្នុង ២nd បញ្ជីយើងមាន ៣ ពី ៣rd បញ្ជីដូច្នេះនៅក្នុងជួរទី ២ និងទី ៦ យើងមានយ៉ាងហោចណាស់ធាតុពីបញ្ជីនីមួយៗ។

ក្បួនដោះស្រាយដើម្បីរកជួរតូចបំផុតដែលមានធាតុពីបញ្ជី 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 លិបិក្រមពីបញ្ជីទាំងអស់ប៉ុន្តែដើម្បីកាត់បន្ថយជួរឱ្យក្លាយទៅជាតូចបំផុតយើងក៏នឹងជំរុញសន្ទស្សន៍ចាប់ផ្តើមផងដែរ។

ជាទូទៅបន្ទាប់ពីរកឃើញធាតុអតិបរិមាយើងនឹងសាងសង់មីនហេប។ ហ៊ាធៀល មុខងារក៏ធ្វើសម្រាប់យើងដែរ។ ឥឡូវមីនហ៊ាបធ្វើកិច្ចការដែលវាបង្កើតប្រភេទអារេដើម្បីផ្ទុកធាតុអប្បបរមាជាមុននិងរៀបចំចំនួនតាមលំដាប់លំដោយតាមរយៈការកសាងហេប។ ដូច្នេះមុខងារនេះធ្វើដូចគ្នាសម្រាប់យើងដែរ។ ប៉ុន្តែយើងត្រូវរកជួរតូចបំផុតទោះបីយើងរកឃើញជួរមួយក៏ដោយ។ យើងត្រូវធ្វើឱ្យប្រាកដថាជាជួរតូចបំផុតដូច្នេះវាអាចទៅរួចយើងអាចធ្វើបច្ចុប្បន្នភាពវា។

យើងនឹងផ្លាស់ប្តូរតម្លៃហើយនៅក្នុងមុខងារ 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]

កម្មវិធីចាវ៉ាដើម្បីស្វែងរកជួរតូចបំផុតដែលមានធាតុពីបញ្ជី 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” គឺជាប្រវែងជួរអាទិភាពដែលនឹងរក្សាទុកធាតុ។