Find Median from Data Stream

Q: Berapa kompleksitas waktu Find Median from Data Stream?

Dengan dua heap, addNum berbiaya O(log n) , paling banyak tiga operasi push atau pop pada heap, dan findMedian berbiaya O(1) , dua operasi baca. Setiap nilai disimpan, jadi penggunaan ruangnya O(n) . Sebagai gantinya, pengurutan pada setiap kueri membutuhkan biaya O(n log n) untuk setiap findMedian .

Q: Mengapa tidak menyimpan nilai-nilainya dalam array yang terurut?

array yang sudah diurutkan menjawab findMedian dalam O(1) , dan binary search menemukan posisi nilai baru dalam O(log n) . Namun, menyisipkannya menggeser setiap nilai setelah posisi itu, O(n) untuk setiap addNum .

SulitHeap

+10

Rancang sebuah struktur dengan dua operasi: addNum menyimpan sebuah bilangan bulat, dan findMedian mengembalikan median dari semua nilai yang telah disimpan sejauh ini. Median untuk jumlah nilai ganjil adalah nilai tengah; untuk jumlah nilai genap, median adalah rata-rata dari dua nilai tengah.

Operasi i adalah ops[i], dengan values[i] berisi angka untuk addNum dan 0 untuk findMedian. Jalankan operasi secara berurutan pada struktur kosong dan kembalikan satu string untuk setiap operasi: "null" untuk addNum, dan median untuk findMedian. Tulis median seperti "3", "2.5" atau "-0.5": tanpa tanda desimal untuk bilangan bulat, dan nol sebagai "0", jangan pernah "-0".

Fungsi

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: operasi, sesuai urutan pelaksanaannya
valuesinteger-array: angka untuk setiap addNum, 0 untuk setiap findMedian
Mengembalikanstring-array: satu jawaban untuk setiap operasi, sebagai teks

Batasan

1 ≤ ops.length ≤ 3000
values.length == ops.length
Setiap ops[i] adalah addNum atau findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ untuk addNum, dan values[i] == 0 untuk findMedian.
findMedian hanya dipanggil setelah setidaknya satu addNum.

Contoh

Input: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Output: ["null", "5", "null", "3", "null", "5", "null", "4"]
Penjelasan: Dengan 1 dan 5, mediannya adalah (1 + 5) / 2 = 3. Dengan 1, 5, dan 8, mediannya adalah 5, dan dengan 1, 3, 5, dan 8, mediannya adalah (3 + 5) / 2 = 4.

Pertanyaan lanjutan

Jika setiap nilai berada di antara 0 dan 100, bagaimana kamu bisa membuat kedua operasi berjalan dalam waktu konstan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Median berada di antara dua bagian data, jadi urutan di dalam masing-masing bagian tidak penting: hanya nilai terbesar dari bagian bawah dan nilai terkecil dari bagian atas yang penting. Dua heap menjaga kedua nilai tersebut tetap berada di puncak. Setiap addNum memerlukan biaya O(log n) dan setiap findMedian membaca dua nilai teratas dalam O(1).

Urutkan pada setiap findMedian

Intuisi

Simpan setiap nilai dalam sebuah list. findMedian mengurutkannya dan membaca indeks (total-1)/2 dan total/2, dengan pembagian bilangan bulat: indeks yang sama untuk jumlah ganjil, pasangan tengah untuk jumlah genap. Jumlahkan kedua nilai lalu bagi dua hasilnya, dan kamu mendapatkan median untuk kedua kasus.

Bagi dua menggunakan bilangan bulat. Jumlah genap habis dibagi. Jumlah ganjil menjadi setengah dari nilai absolutnya diikuti .5, dengan tanda sesuai jumlahnya, jadi -3 menjadi -1.5.

Setiap query mengurutkan lagi. Dengan 1,500 penambahan dan satu query setelah setiap penambahan, jumlahnya sekitar 10^7 perbandingan, sedangkan heap memerlukan beberapa puluh ribu langkah.

Algoritma

Simpan sebuah list values.
Untuk addNum x, tambahkan x dan catat "null".
Untuk findMedian, urutkan values dan tambahkan values[(total-1)/2] dan values[total/2].
Bagi dua jumlahnya sebagai teks dengan bilangan bulat, lalu catat hasilnya.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Dua heap yang dipisahkan pada median

Intuisi

Pisahkan nilai menjadi bagian bawah low dan bagian atas high, dengan setiap nilai di low paling besar sama dengan setiap nilai di high, serta ukuran low sama dengan ukuran high atau lebih besar satu. Median adalah nilai terbesar di low, atau untuk jumlah genap, rata-rata nilai tersebut dengan nilai terkecil di high. Max-heap untuk low dan min-heap untuk high menjaga nilai-nilai tersebut tetap di posisi teratas.

Nilai baru dimasukkan ke low jika nilainya paling besar sama dengan nilai teratas low, jika tidak, masukkan ke high. Saat ukurannya mulai berbeda, pindahkan nilai teratas dari satu bagian ke bagian lain: nilai tersebut paling dekat dengan bagian lain, sehingga urutannya tetap terjaga. Operasi penambahan memerlukan beberapa operasi heap, O(log n), atau O(n) di R, yang menyalin heap setiap kali ada perubahan.

Setelah empat penambahan pada contoh pertama, low berisi 3 dan 1, sedangkan high berisi 5 dan 8.

Algoritma

Pertahankan max-heap low untuk separuh bagian bawah dan min-heap high untuk separuh bagian atas.
addNum x: masukkan x ke low jika low kosong atau x paling besar sama dengan elemen teratasnya, jika tidak, masukkan ke high.
Jika low menampung dua nilai lebih banyak daripada high, pindahkan elemen teratas low ke high. Jika high menampung lebih banyak nilai daripada low, pindahkan elemen teratas high ke low.
findMedian: jika low lebih besar, catat elemen teratasnya. Jika tidak, jumlahkan kedua elemen teratas lalu bagi dua dengan pembagian bilangan bulat.

import heapq


def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Jebakan dan kasus tepi

Memilih heap berdasarkan ukurannya, bukan nilainya. Menambahkan nilai ke heap yang lebih kecil tanpa membandingkannya akan merusak urutan antara kedua bagian, sehingga nilai teratasnya bukan lagi nilai tengah.
Membagi dua dengan pembagian bilangan bulat biasa. Dalam C dan Java, -1 / 2 bernilai 0, jadi menambahkan .5 akan mencetak 0.5 untuk -0.5. Dalam Python, -3 // 2 bernilai -2, sehingga mencetak -2.5 untuk -1.5. Bilangan floating point dicetak sebagai 3.0 atau 2.500000 dalam beberapa bahasa.
Menyimpan low dalam bentuk negatif di min-heap dan lupa mengubahnya kembali menjadi positif saat membaca nilai teratasnya atau memindahkan nilai ke high.
Menulis -0. Nilai tengah -1 dan 1 berjumlah 0, dan jawabannya adalah "0".

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Find Median from Data Stream?

Dengan dua heap, addNum berbiaya O(log n), paling banyak tiga operasi push atau pop pada heap, dan findMedian berbiaya O(1), dua operasi baca. Setiap nilai disimpan, jadi penggunaan ruangnya O(n). Sebagai gantinya, pengurutan pada setiap kueri membutuhkan biaya O(n log n) untuk setiap findMedian.

Mengapa tidak menyimpan nilai-nilainya dalam array yang terurut?

array yang sudah diurutkan menjawab findMedian dalam O(1), dan binary search menemukan posisi nilai baru dalam O(log n). Namun, menyisipkannya menggeser setiap nilai setelah posisi itu, O(n) untuk setiap addNum.

Bisakah kamu menemukan median yang tepat dari sebuah aliran data tanpa menyimpan setiap nilai?

Tidak secara umum. Nilai apa pun yang sudah terlihat sejauh ini bisa menjadi median nanti, bergantung pada apa yang datang berikutnya, jadi jawaban yang tepat memerlukan semuanya.

def medianStreamOps(ops, values):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

Output yang diharapkan

["null", "5", "null", "3", "null", "5", "null", "4"]