Find Median from Data Stream
İki işlem içeren bir yapı tasarlayın: addNum bir tam sayı depolar ve findMedian şimdiye kadar depolanan tüm değerlerin medyanını döndürür. Tek sayıda değer varsa medyan ortadaki değerdir; çift sayıda değer varsa ortadaki iki değerin ortalamasıdır.
i işlemi ops[i] şeklindedir; addNum için sayıyı values[i], findMedian için ise 0 içerir. İşlemleri boş bir yapı üzerinde sırasıyla çalıştırın ve her işlem için bir dize döndürün: addNum için "null", findMedian için medyan. Medyanı "3", "2.5" veya "-0.5" biçiminde yazın: tam sayıysa ondalık nokta kullanmayın; sıfır için "0" yazın, asla "-0" yazmayın.
Fonksiyon
- opsstring-array
- işlemler, çalıştırıldıkları sırayla
- valuesinteger-array
- her addNum için sayı, her findMedian için 0
- Döndürürstring-array
- işlem başına metin olarak bir yanıt
Kısıtlar
1 ≤ ops.length ≤ 3000values.length == ops.length- Her
ops[i],addNumveyafindMedianolur. -105 ≤ values[i] ≤ 105addNumiçin vevalues[i] == 0findMedianiçin.findMedianyalnızca en az biraddNumçağrıldıktan sonra çağrılır.
Örnekler
- Girdi
- ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
- Çıktı
- ["null", "5", "null", "3", "null", "5", "null", "4"]
- Açıklama
- 1 ve 5 için medyan (1 + 5) / 2 = 3'tür. 1, 5 ve 8 için medyan 5'tir; 1, 3, 5 ve 8 için ise (3 + 5) / 2 = 4'tür.
- Girdi
- ops = ["addNum", "addNum", "findMedian", "addNum", "addNum", "findMedian"]values = [-4, 3, 0, -2, -1, 0]
- Çıktı
- ["null", "null", "-0.5", "null", "null", "-1.5"]
- Açıklama
- -4 ile 3'ün toplamı -1 olduğundan medyan -0.5'tir. -2 ve -1'den sonra sıralı değerler -4, -2, -1, 3 olur; ortadaki çiftin toplamı -3 olduğundan medyan -1.5'tir.
Ek soru
Her değer 0 ile 100 arasında olsaydı, her iki işlemin de sabit zamanda çalışmasını nasıl sağlayabilirdin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her
findMediançağrısında tüm değerleri sıralamak doğrudur, ancak çok fazla işi tekrarlar. Medyan yalnızca ortadaki değere bakar. Hangi değerleri hızlıca bulmanız gerçekten gerekiyor?Değerleri alt yarı ve üst yarı olarak ayırın. Medyan yalnızca alt yarıdaki en büyük değere ve üst yarıdaki en küçük değere bağlıdır; her yarının kendi içindeki sıralama önemli değildir.
Alt yarıyı bir max-heap'te, üst yarıyı ise bir min-heap'te tut; alt yarıda, üst yarıdaki kadar veya bir fazla değer bulunsun. Her yeni değeri alt yarının tepe değeriyle karşılaştırarak doğru tarafa yerleştir, ardından boyutlar dengesizleşirse bir tepe değerini diğer tarafa taşı.
Çözüm
Medyan, verilerin iki yarısının arasında yer alır; bu nedenle her yarının kendi içindeki sıralama önemli değildir: yalnızca alt yarının en büyük değeri ve üst yarının en küçük değeri önemlidir. İki yığın, tam olarak bu iki değeri en üstte tutar. Her addNum işlemi O(log n) maliyetindedir ve her findMedian işlemi O(1) sürede iki tepedeki değeri okur.
Her findMedian çağrısında sıralama
Sezgi
Her değeri bir listede sakla. findMedian listeyi sıralar ve tam sayı bölmesiyle (total-1)/2 ve total/2 indislerindeki değerleri okur: tek sayıda aynı indis, çift sayıda ise ortadaki ikili. İki değeri toplayıp toplamı ikiye bölersen her iki durumda da medyanı elde edersin.
Tam sayılarla ikiye böl. Çift bir toplam tam bölünür. Tek bir toplam, mutlak değerinin yarısı ve ardından .5 olacak şekilde, toplamın işaretiyle birlikte ifade edilir; bu nedenle -3, -1.5 olur.
Her sorgu listeyi yeniden sıralar. 1,500 ekleme ve her birinin ardından bir sorgu yapıldığında bu, yaklaşık 10^7 karşılaştırma demektir; yığınlar ise birkaç on bin adım gerektirir.
Algoritma
valuesadlı bir liste tut.addNum xiçinx'i ekle ve"null"kaydet.findMedianiçinvalues'i sırala vevalues[(total-1)/2]ilevalues[total/2]değerlerini ekle.- Toplamı, tam sayılarla metin olarak ikiye böl ve kaydet.
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 resultMedyan noktasında ayrılan iki yığın
Sezgi
Değerleri, low alt yarısına ve high üst yarısına ayır; low'daki her değer, high'daki her değerden küçük veya ona eşit olsun ve low, high ile aynı boyutta ya da bir eleman daha büyük olsun. Medyan, low'daki en büyük değerdir; eleman sayısı çiftse low'daki en büyük değer ile high'daki en küçük değerin ortalamasıdır. low için bir maksimum yığın ve high için bir minimum yığın kullanmak, bu değerleri yığınların tepesinde tutar.
Yeni bir değer, low'un tepesindeki değerden küçük veya ona eşitse low'a, aksi hâlde high'a eklenir. Boyutlar birbirinden farklılaştığında, tepedeki bir değeri diğer tarafa taşı; bu, diğer yarıya en yakın değerdir, dolayısıyla sıralama korunur. Ekleme birkaç yığın işlemi gerektirir: O(log n); her değişiklikte yığını kopyalayan R'de ise O(n).
İlk örnekteki dört eklemeden sonra low, 3 ve 1'i; high ise 5 ve 8'i içerir.
Algoritma
- Alt yarı için bir max-heap
low, üst yarı için bir min-heaphightut. addNum x:lowboşsa veyaxen üstündeki değerden küçük ya da ona eşitsexdeğerinilowiçine, aksi hâldehighiçine ekle.low,high'dan iki fazla değer içeriyorsalow'un en üstündeki değerihigh'a taşı.high,low'dan daha fazla değer içeriyorsahigh'ın en üstündeki değerilow'a taşı.findMedian:lowdaha büyükse en üstündeki değeri kaydet. Aksi hâlde en üstteki iki değeri topla ve toplamı tam sayılarla ikiye böl.
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
Tuzaklar ve uç durumlar
- Yığıtları değere göre değil, boyuta göre seçmek. Karşılaştırmadan daha küçük yığıta ekleme yapmak, iki yarı arasındaki sıralamayı bozar ve en üstteki değerler artık ortadaki değerler olmaz.
- Normal tamsayı bölmesiyle ikiye bölmek. C ve Java'da
-1 / 20'dır; bu nedenle.5eklemek, -0.5 için 0.5 yazdırır. Python'da-3 // 2-2'dir; bu da -1.5 için -2.5 yazdırır. Bazı dillerde kayan noktalı sayılar 3.0 veya 2.500000 yazdırır. lowdeğerini bir min-yığında negatif olarak saklamak ve en üstteki değeri okurken veya bir değerihigh'a taşırken işaretini tekrar negatife çevirmeyi unutmak.-0yazmak. Ortadaki -1 ve 1 değerlerinin toplamı 0'dır ve yanıt"0"olur.
Sıkça sorulan sorular3
Veri Akışından Medyan Bulma işleminin zaman karmaşıklığı nedir?
İki yığınla addNum, en fazla üç yığın ekleme veya çıkarma işlemiyle O(log n) maliyetindedir ve findMedian, iki okuma işlemiyle O(1) maliyetindedir. Her değer saklandığından, alan kullanımı O(n) olur. Bunun yerine her sorguda sıralama yapmak, findMedian başına O(n log n) maliyetine yol açar.
Neden değerleri sıralanmış bir dizide tutmayalım?
Sıralanmış bir dizi, findMedian sorgusunu O(1) sürede yanıtlar ve ikili arama, yeni bir değerin nereye yerleşeceğini O(log n) sürede bulur. Ancak bu değeri eklemek, o noktadan sonraki tüm değerleri kaydırır; her addNum işlemi için O(n).
Her değeri saklamadan bir akışın tam medyanını bulabilir misin?
Genel olarak hayır. Şimdiye kadar görülen herhangi bir değer, daha sonra ortanca olabilir; bu, sırada neyin geleceğine bağlıdır. Bu nedenle kesin bir yanıt için hepsine ihtiyaç vardır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def medianStreamOps(ops, values):
# Kodu buraya yazınTest #1
Test #2
Argümanlar
ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"] values = [5, 0, 1, 0, 8, 0, 3, 0]
Beklenen Çıktı
["null", "5", "null", "3", "null", "5", "null", "4"]