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/

相关文章:

Python: concurrent.futures 如何让它可取消?

python - 如何将 celery 应用程序与 Task 类绑定(bind)?

algorithm - 有 n 个节点的无向​​图中的最大边数是多少?

algorithm - 为什么这不能递归工作?

MYSQL QUERY 计数,如何进行?

php - 我可以计算每个 MySQL Select/Union 有多少结果吗

python - 从 numpy 数组创建 pandas DataFrame 会导致奇怪的错误

python - 如何根据mysql结果数据使用python中的条件打印数据

algorithm - 根据高度重新排列人员的算法是否正确?

PHP 计数数组元素