假设在数组的每一行中,所有 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/