c++ - 如何在没有蛮力的情况下找到矩阵中元素的计数？我们可以这样做吗？

Question

我想检查给定数组（2D）中是否存在元素，并找到单元格左侧和单元格右侧以及顶部和底部的计数。我如何在不使用蛮力的情况下做到这一点力量

Answer 1

除了其他答案（可能对任何当前的应用程序都不是很有用，只是一个想法）之外，还有 Grover 的算法。来自维基百科的努力：

Grover 算法是一种量子算法，用于在 O(N1/2) 时间内搜索具有 N 个条目的未排序数据库，并使用 O(log N) 存储空间（参见大 O 表示法）。洛夫格罗弗在 1996 年制定了它。

在经典计算模型中，搜索未排序的数据库不能在少于线性的时间内完成（因此仅搜索每个项目是最佳的）。Grover 的算法说明在量子模型中搜索可以比这更快地完成；事实上，它的时间复杂度 O(N1/2) 是在线性量子模型中搜索未排序数据库时渐近最快的。

Answer 2

如果数组已排序，那么您可以使用二进制搜索找到 O(nlogm) 时间复杂度！其中 n,m 是行和列。

Answer 3

如果你的矩阵是未排序的，并且你没有像哈希表这样的东西来快速访问，那就没有办法了。

例如，如果您的矩阵已排序，则可以使用更有效的搜索算法（例如二分搜索）来更快地找到元素。不要忘记，二维数组可以用一个向量和一个保存列数的变量来表示。