2

だから私はこのコードを書いて、それは最初のテストケースに合格し、残りはすべて失敗しました。ただし、それを壊す入力が見つからないようです。コードを長時間見つめていたせいかもしれませんが、助けていただければ幸いです。このアルゴリズムは、現在のリストの最小半分と最大半分に対して 2 つの優先キューを使用します。コードは次のとおりです。

#!/bin/python
import heapq

def fix(minset, maxset):
    if len(maxset) > len(minset):
        item = heapq.heappop(maxset)
        heapq.heappush(minset, -item)
    elif len(minset) > (len(maxset) + 1):
        item = heapq.heappop(minset)
        heapq.heappush(maxset, -item)

N = int(raw_input())

s = []
x = []

for i in range(0, N):

        tmp = raw_input()
        a, b = [xx for xx in tmp.split(' ')]
        s.append(a)
        x.append(int(b))

minset = []
maxset = []

for i in range(0, N):
    wrong = False
    if s[i] == "a":
        if len(minset) == 0:
            heapq.heappush(minset,-x[i])
        else:
            if x[i] > minset[0]:
                heapq.heappush(maxset, x[i])
            else:
                heapq.heappush(minset, -x[i])
        fix(minset, maxset)
    elif s[i] == "r":
        if -x[i] in minset:
            minset.remove(-x[i])
            heapq.heapify(minset)
        elif x[i] in maxset:
            maxset.remove(x[i])
            heapq.heapify(maxset)
        else:
            wrong = True
        fix(minset, maxset)
    if len(minset) == 0 and len(maxset) == 0:
        wrong = True

    if wrong == False:
        #Calculate median
        if len(minset) > len(maxset):
            item = - minset[0]
            print int(item)
        else:
            item = ((-float(minset[0])) + float(maxset[0])) / 2
            if item.is_integer():
                print int(item)
                continue
            out =  str(item)
            out.rstrip('0')
            print out
    else:
        print "Wrong!"
4

1 に答える 1

0

あなたのオリジナルはそれほど読みにくいので、最初に私はそれをオブジェクト指向にしました： MedianHeapqメソッドをサポートしますrebalance(), add(), remove(), size(), median()。minset,maxsetあらゆる種類の賢明な理由で、メンバーをクライアントコードから隠したいのです。クライアントがメンバーを交換したり、変更したりしないようにします。クライアントがメンバーを表示する必要がある場合は、アクセサーを作成するだけです。__str__()また、視覚的にデバッグして作業を楽にするために使用するメソッドを追加しました。

[i]また、どこでも索引付けを回避するための読みやすさの変更を追加s,xし、配列の名前をに変更しop,val、プロンプトを追加raw_input()し、入力ステージで無効な操作を拒否します。中央値の実際の計算は私を混乱させます（いつfloatが必要で、いつ整数が必要ですか？これrstrip('0')は少し奇抜です）。それで書き直しました。何か他のものが必要な場合は変更してください。アルゴリズムの説明はここにあります。

今では読みやすく、自己完結型です。また、テスト可能になります。コードで符号エラーが発生している可能性があります。わかりません。後で説明します。次に、いくつかのPyUnitテストケースを作成して自動化します。doctestも可能です。TBC。

わかりました、中央値を見つけることについてのだらしなさのバグを見たと思います。minsetとmaxsetのサイズの不一致は+/-1である可能性があることに注意してください。したがって、中央値がどこにあるかについてはもっと注意してください。

#!/bin/python
import heapq    

class MedianHeapq(object):
    def __init__(self):
        self.minset = []
        self.maxset = []        
    def rebalance(self):
        size_imbalance = len(self.maxset) - len(self.minset)
        if len(self.maxset) > len(self.minset):
        #if size_imbalance > 0:
            item = heapq.heappop(self.maxset)
            heapq.heappush(self.minset, -item)
        #elif size_imbalance < -1:
        elif len(self.minset) > (len(self.maxset) + 1):
            item = heapq.heappop(self.minset)
            heapq.heappush(self.maxset, -item)
    def add(self, value, verbose=False):
        if len(self.minset) == 0:
            heapq.heappush(self.minset,-value)
        else:
            if value > self.minset[0]:
                heapq.heappush(self.maxset, value)
            else:
                heapq.heappush(self.minset, -value)
        self.rebalance()
        if verbose: print self.__str__()
        return False
    def remove(self,value,verbose=False):
        wrong = False
        if -value in self.minset:
            minset.remove(-value)
            heapq.heapify(self.minset)
        elif value in maxset:
            maxset.remove(value)
            heapq.heapify(self.maxset)
        else:
            wrong = True
        self.rebalance()
        if verbose: print self.__str__()
        return wrong
    def size(self):
        return len(self.minset)+len(self.maxset)
    def median(self):
        if len(self.minset) > len(self.maxset):
            item = - self.minset[0]
            return int(item)
        else:
            item = (-self.minset[0] + self.maxset[0]) / 2.0
            # Can't understand the intent of your code here: int, string or float?
            if item.is_integer():
                return int(item)
            #    continue # intent???
            else:
               return item
            # The intent of this vv seems to be round floats and return '%.1f' % item ?? 
            #out =  str(item)
            #out.rstrip('0') # why can't you just int()? or // operator?
            #return out


    def __str__(self):
        return 'Median: %s Minset:%s Maxset:%s' % (self.median(), self.minset,self.maxset)

# Read size and elements from stdin
N = int(raw_input('Size of heap? '))
op = []
val = []
while(len(val)<N):
        tmp = raw_input('a/r value : ')
        op_, val_ = tmp.split(' ')
        if op_ not in ['a','r']: # reject invalid ops
            print 'First argument (operation) must be a:Add or r:Remove! '
            continue
        op.append(op_)
        val.append(int(val_))

mhq = MedianHeapq()
for op_,val_ in zip(op,val): # use zip to avoid indexing with [i] everywhere
    wrong = False
    if op_ == 'a':
        wrong = mhq.add(val_)
    elif op_ == 'r':
        wrong = mhq.remove(val_)

    assert (mhq.size()>0), 'Heap has zero size!'

    assert (not wrong), 'Heap structure is wrong!'

    if not wrong:
        print mhq.__str__()
于 2012-08-26T05:13:06.930 に答える