所以我写了这段代码,它通过了第一个测试用例,其余的都失败了。但是,我似乎找不到打破它的输入。也许是因为我盯着代码看的时间太长了,但我会很感激任何帮助。 该算法对当前列表的最小和最大一半使用两个优先级队列。这是代码:
#!/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!"
最佳答案
你的原文不是那么清晰,所以首先我让它面向对象:
MedianHeapq
支持方法 rebalance()、add()、remove()、size()、median()
。我们非常想从客户端代码中隐藏成员 minset,maxset
,出于各种合理的原因:防止客户端交换它们、修改它们等。如果客户端需要看到它们,您只需编写一个访问器.
我们还添加了一个 __str__()
方法,我们将使用该方法进行可视化调试,让您的生活更轻松。
还添加了易读性更改以避免到处使用 [i]
进行索引,将 s,x
数组重命名为 op,val
,添加提示在 raw_input()
上,拒绝输入阶段的无效操作。
你对中位数的实际计算让我很困惑(你什么时候需要 float ,什么时候需要整数?rstrip('0')
有点古怪),所以我重写了它,如果你想要别的东西,就改变它.
该算法的讨论是 here .
现在它清晰易读且独立。也使其可测试。 您可能在代码中犯了符号错误,我不知道,我稍后再看。 接下来我们要通过编写一些 PyUnit 测试用例来自动化它。 doctest 也是一种可能性。待定。
好吧,我想我看到了关于定位中位数的草率错误。请记住,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__()
关于python - Python 中的 Inteviewstreet 中位数。除了第一个测试用例之外的所有测试都失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11934064/