Data Stream LeetCode Həllindən Medianı tapın

Problem bəyanat

Data Stream LeetCode Həllindən Medianı tapın – The median sıralı tam siyahıda orta qiymətdir. Siyahının ölçüsü bərabərdirsə, orta qiymət yoxdur və median iki orta qiymətin ortasıdır.

• Məsələn, arr = [2,3,4], mediandır 3.
• Məsələn, arr = [2,3], mediandır (2 + 3) / 2 = 2.5.

MedianFinder sinfini həyata keçirin:

• MedianFinder() başlatır MedianFinder obyekt.
• void addNum(int num) tam ədədi əlavə edir num məlumat axınından məlumat strukturuna qədər.
• double findMedian() indiyə qədər bütün elementlərin medianı qaytarır. Cavablar daxilində 10^-5 faktiki cavab qəbul olunacaq.

misal

Test işi 1:

Input:

[“MediaFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]

[[], [1], [2], [], [3], []]

Çıxış:

[null, null, null, 1.5, null, 2.0]

Explanation:

MedianFinder medianFinder = yeni MedianFinder();

medianFinder.addNum(1); // arr = [1]

medianFinder.addNum(2); // arr = [1, 2]

medianFinder.findMedian(); // 1.5 qaytarın (yəni, (1 + 2) / 2)

medianFinder.addNum(3); // arr[1, 2, 3]

medianFinder.findMedian(); // 2.0 qaytarın

Yanaşma:

Alqoritmin invariantı hər biri cari siyahının yarısını təmsil edən kiçik və böyük iki yığındır. Kiçik yarının uzunluğu hər zaman n / 2 olaraq saxlanılır və böyük yarının uzunluğu n paritetindən asılı olaraq ya n / 2, ya da n / 2 + 1 olur.

Bu yolla medianı hesablamaq üçün yalnız iki üst ədəd yığınına nəzər salmalıyıq.

Yeni nömrə əlavə etməzdən əvvəl istənilən vaxt iki ssenari var (cəmi n ədəd, k = n / 2):

(<span class="hljs-number">1</span>) <span class="hljs-function">length <span class="hljs-title">of</span> <span class="hljs-params">(small, large)</span> </span>== (k, k)
(<span class="hljs-number">2</span>) <span class="hljs-function">length <span class="hljs-title">of</span> <span class="hljs-params">(small, large)</span> </span>== (k, k + <span class="hljs-number">1</span>)

Nömrəni, cəmi (n + 1) ədədləri əlavə etdikdən sonra onlar olacaq:

(<span class="hljs-number">1</span>) <span class="hljs-function">length <span class="hljs-title">of</span> <span class="hljs-params">(small, large)</span> </span>== (k, k + <span class="hljs-number">1</span>)
(<span class="hljs-number">2</span>) <span class="hljs-function">length <span class="hljs-title">of</span> <span class="hljs-params">(small, large)</span> </span>== (k + <span class="hljs-number">1</span>, k + <span class="hljs-number">1</span>)

Burada birinci ssenarini götürürük, məsələn, biz bilirik ki, böyük bir element daha qazanacaq, kiçik isə eyni ölçüdə qalacaq, lakin biz elementi sadəcə böyükə itələyə bilmərik. Etməli olduğumuz şey, yeni nömrəni kiçikə itələmək və maksimum elementi kiçikdən çıxarmaq, sonra onu böyütməkdir (burada bütün pop və təkanlar yığın və yığındır). İki ssenari üçün bu cür əməliyyat etməklə biz invariantımızı saxlaya bilərik.

Buna görə ədədi əlavə etmək üçün 3 O(log n) yığın əməliyyatımız var. Xoşbəxtlikdən heapq bizə “heappushpop” funksiyasını təqdim etdi ki, bu da ikisini bir yerə birləşdirərək bir qədər vaxta qənaət edir. Sənəddə deyilir:

Elementi yığının üzərinə itələyin, sonra yığışdırın və yığından ən kiçik elementi qaytarın. Birləşdirilmiş hərəkət heappush()-dan daha səmərəli işləyir və sonra heappop()-a ayrıca zəng edir.

Ümumilikdə əlavə əməliyyatı O(logn) və tap medianı əməliyyatı O(1)-dir.

Qeyd edək ki, python-da heapq min-heapdır, ona görə də “maksimum yığın”ı təqlid etmək üçün kiçik yarıdakı dəyərləri tərsinə çevirməliyik.

Data Stream-dən Medianı tapmaq üçün kod

Java Proqramı

class MedianFinder {

    private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> large = new PriorityQueue<>();
    private boolean even = true;

    public double findMedian() {
        if (even)
            return (small.peek() + large.peek()) / 2.0;
        else
            return small.peek();
    }

    public void addNum(int num) {
        if (even) {
            large.offer(num);
            small.offer(large.poll());
        } else {
            small.offer(num);
            large.offer(small.poll());
        }
        even = !even;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

Python proqramı

from heapq import *


class MedianFinder:
    def __init__(self):
        self.small = []  # the smaller half of the list, max heap (invert min-heap)
        self.large = []  # the larger half of the list, min heap

    def addNum(self, num):
        if len(self.small) == len(self.large):
            heappush(self.large, -heappushpop(self.small, -num))
        else:
            heappush(self.small, -heappushpop(self.large, num))

    def findMedian(self):
        if len(self.small) == len(self.large):
            return float(self.large[0] - self.small[0]) / 2.0
        else:
            return float(self.large[0])

Data Stream LeetCode Həllindən Median Tapmaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O(logn), ən pis halda, yuxarıdan üç yığın əlavəsi və iki yığın silinməsi var. Bunların hər biri təxminən edir $O(daxil\; oln)$ vaxt..

Kosmik Mürəkkəblik: O(n), çünki biz konteynerlərdə girişi saxlamaq üçün xətti boşluqdan istifadə edirik.