我正在尝试解决以下问题:
一队急切的个位数(您的输入)正在等待进入空房间。
我允许一个数字(从左边)每分钟进入房间。
每次新数字进入房间时,我在黑板上记录当前所有数字的中位数。[中位数是按升序排列时的中间数字。]。如果有两个中位数(即两个中间数),则不使用平均值,而是记录其中较小的一个。
我将新数字写在现有数字的右侧,因此我的黑板数字不断变长。
当所有数字都在房间里时,您的黑板上最终会出现什么数字?
考虑以下示例输入:21423814127333
- 2(最左边的数字)被允许进入房间,因此我在黑板上写上2。
- 接下来1被允许进入房间与2一起。这两个数字中较小的一个被用作中位数,因此我在黑板上将1标记在2的右侧(我的数字现在是21)
- 现在4进入了房间。1、2和4的中位数是2,因此我在黑板上添加2(我的数字现在是212)
- ...这个过程一直持续到最后3进入房间...所有数字现在都在房间里,经排序后分别为1,1,1,2,2,2,3,3,3,3,4,7,8,8.有两个中位数,但它们都是3,因此我在黑板上加上3,我的最终数字是21222222222233。
我的当前解决方案:
num = input()
new = str(num[0])
whole = [num[0]]
for i in range(1, len(num)):
whole.append(num[i])
whole.sort()
new += whole[i//2]
print(new)
问题在于它花费的时间太长了 - 因此它通过了6/10(隐藏)测试用例,但超出了其他4个的时间限制。任何帮助将不胜感激。
bisect
模块可以帮助实现这一点。 - Tim Roberts