Kth أكبر عنصر في حل Leetcode التدفق  


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل صندوق يباي Facebook جولدمان ساكس جوجل Microsoft Nutanix
خوارزمية خوارزميات الترميز تصميم كومة المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions

المشكلة بيان  

في هذه المشكلة ، علينا تصميم فصل دراسي KthLargest () الذي يحتوي في البداية على عدد صحيح ك و مجموعة من الأعداد الصحيحة. نحتاج إلى كتابة مُنشئ معلمات له عندما يكون عددًا صحيحًا k ومصفوفة NUMS يتم تمريرها كحجج. الفصل أيضا له وظيفة add (val) يضيف عنصرًا جديدًا ذا قيمة فال في تيار الأعداد الصحيحة. لكل إضافة () call ، نحتاج إلى إرجاع عدد صحيح يمثل أكبر عنصر Kth في التدفق الجاري.

مثال

["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
4 5 5 8 8

التفسير:

Kth أكبر عنصر في حل Leetcode التدفق

نهج (أقل أكوام)  

عندما يتعلق الأمر بالعثور على عنصر Kth الأصغر / الأكبر ، فإن max / min heaps تقريبًا في كل مرة تخدم الغرض. هذا بسبب طبيعتها المرنة للاحتفاظ بالعناصر بطريقة مرتبة (حسب الأولوية). هنا ، يمكننا أيضًا استخدام مصفوفة لاحتواء العناصر كلما تم إجراء استعلام. ولكن من أجل العثور على ملف كته أكبر عنصر في المصفوفة، يجب علينا استخدام وقت O (N) لكل استعلام. لذلك ، يمكننا الاحتفاظ بأدنى حجم كومة من الحجم k لإيجاد أكبر عنصر k في زمن O (1). لاحظ أنه نظرًا لأننا نستخدم min-heap ، فإن العنصر الأعلى سيكون الأصغر في الكومة. ونظرًا لأننا ربطنا حجم الكومة ليكون مساويًا لـ k بعد كل استعلام ، فسيكون هذا العنصر العلوي هو Kth الأكبر في التدفق الكلي (حيث أن الكومة ستحتفظ بـ k أكبر العناصر فقط).

انظر أيضا
أبطأ حل Leetcode مفتاح

تنفيذ Kth أكبر عنصر في حل Leetcode التدفق

برنامج C ++

#include <bits/stdc++.h>

using namespace std;

class KthLargest {
public:
    priority_queue <int , vector <int> , greater <int> > pq;
    int K;

    KthLargest(int k, vector<int>& nums) {
        K = k;
        for(int &x : nums) {
            pq.push(x);
            if(pq.size() > k) {
                pq.pop();
            }
        }
    }

    int add(int val) {
        pq.push(val);
        if(pq.size() > K)
            pq.pop();
        return pq.top();
    }
};

int main() {
    vector <int> nums = {4 , 5 , 8 , 2};
    int k = 3;
    KthLargest stream(k , nums);
    cout << stream.add(3) << " ";
    cout << stream.add(5) << " ";
    cout << stream.add(10) << " ";
    cout << stream.add(9) << " ";
    cout << stream.add(4) << " ";
    cout << endl;
    return 0;
}

برنامج جافا

import java.util.*;
import java.io.*;

class comp implements Comparator<Integer> {
    public int compare(Integer a , Integer b) {
        if(a > b)
            return 1;
        if(a < b)
            return -1;
        return 0;
    }
}

class KthLargest {
    int K;
    PriorityQueue <Integer> pq;

    public KthLargest(int k, int[] nums) {
        K = k;
        pq = new PriorityQueue <Integer> (new comp());
        for(int x : nums) {
            pq.add(x);
            if(pq.size() > k) {
                pq.remove();
            }
        }
    }

    int add(int val) {
        pq.add(val);
        if(pq.size() > K)
            pq.remove();
        return pq.peek();
    }
}

class KthLargestInStream {
    public static void main(String args[]) {
        int k = 3;
        int[] nums = {4 , 5 , 8 , 2};
        KthLargest stream = new KthLargest(k , nums);
        System.out.print(stream.add(3) + " ");
        System.out.print(stream.add(5) + " ");
        System.out.print(stream.add(10) + " ");
        System.out.print(stream.add(9) + " ");
        System.out.print(stream.add(4) + " ");
        System.out.println();
    }
}
4 5 5 8 8

تحليل التعقيد لأكبر عنصر Kth في حل Leetcode التدفق

تعقيد الوقت

يا (N + Q)، حيث N = حجم المصفوفة الأولية (أثناء استدعاء المُنشئ). Q = عدد الاستفسارات. هذا لأننا نجتاز المصفوفة مرة واحدة ونجيب على كل استعلام في وقت O (1).

تعقيد الفضاء 

نعم)، حيث K هي الحجة المعطاة (أثناء استدعاء المنشئ). هذا لأننا نحافظ على حجم الكومة ليكون بالضبط k ، بعد أي مجموعة من العمليات.

انظر أيضا
قم بإجراء تحويلات السلسلة Leetcode