python - 计数 1's in a n x n array of 0' 和 1

标签 python algorithm count

假设在数组的每一行中,所有 1 都在 0 之前,我如何才能想出 (O)nlogn 算法来计算数组中的 1。我想首先我必须制作一个计数器,在每一行中搜索 1 (n),然后将其添加到计数器中。 “log n 部分”在哪里发挥作用?我读到执行此操作的递归算法具有 nlogn 复杂性,但我不太确定我将如何执行此操作。我知道如何使用 for 循环在 O(n^2) 中执行此操作。伪代码或提示会有所帮助!谢谢

最佳答案

由于所有 1 都在 0 之前,您可以使用二进制搜索算法(即 log N)找到第一个 0 的索引,您只需对所有 N 行执行此操作。所以总的复杂度是 NlogN。

关于python - 计数 1's in a n x n array of 0' 和 1,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23001932/

相关文章:

algorithm - Bellman-Ford 算法的中间最优性,是否正确?

python - 让 matplotlib 渲染用鼠标点击的点。

linux - 有没有办法在 CentOS 中计算每秒文件中添加的行数?

mysql - SQL 按匹配特定行排序

python - Google Python API 尝试导入已弃用的 oauth2client.contrib.multistore_file

python - 为什么python有前自增操作符而没有后自增操作符?

python - Cooley-Tukey 算法 python 超出范围

mysql - 如何计算多个表?

python - PyQt6 在同一窗口中跨选项卡实现复制粘贴功能

python - 在下拉菜单或用户单击时填充 QComboBox