python - 计数反转而不迭代两次
问题描述
问题可以在这里找到。这是我尝试过的,但我得到了错误的答案。我的逻辑是这样的。在任何时候,如果排序队列和状态队列中的位置之间的差异为负,那么我们将差异的绝对值添加到混沌中。现在,如果我面临两个连续的正差,并且前一个位置的数字大于状态队列中的当前数字,我将混乱加 1。
def minimumBribes(q):
truth = None
old = 0
chaos = 0
for i in range(len(q)):
diff = (i+1)-q[i]
if diff < -2:
print("Too chaotic")
return
if diff < 0 :
chaos = chaos + abs(diff)
truth = True
continue
else:
if truth == True:
truth = False
old = q[i]
continue
if old > q[i]:
chaos = chaos + 1
old = q[i]
print(chaos)
解决方案
无法通过比较计算线性时间的倒数。它有一个理论上的界限。https://cs.stackexchange.com/questions/74515/can-we-count-the-number-of-inversions-in-time-mathcalon
您可以使用 Fenwick 树(也称为二进制索引树)来解决它。这里描述了这个想法(https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/)。
推荐阅读
- php - 如何从带有进度条ajax的laravel中偏移的分页JSON响应中循环
- javascript - 'ckeditor4-react' 和 'HTML5 video' 插件
- haskell - 使用带有 Parsec 的累加器进行 Haskell 解析
- r - 在 R 的 strplit() 函数中:添加索引值有什么区别?
- c++ - 使用堆栈上的数组对结构进行默认初始化
- angular - 如何将 Angular Bootstrap 表“完整示例”与实际服务一起使用?
- git - 如何将所有 repo 的提交与新电子邮件相关联?
- r - 如何使 R 函数中的数据框可全局访问?
- python - Jupyter Notebook Python error: tuple index out of range
- spring - Spring batch chunk based approach for calling REST API in Item Writer