关于如何快速搜索二维数组有什么想法吗？
我像这样写了一个二维数组，就像一个矩阵：（
{{1, 2, 4, 5, 3, 6},
{8, 3, 4, 4, 5, 2},
{8, 3, 4, 2, 6, 2},
//code skips... ...
}
数组未排序） 我想得到所有“4”的位置，而不是一一搜索数组，并返回位置，如何才能更快/更高效地搜索它？提前谢谢。
I jave a 2D array like this, just like a matrix:
{{1, 2, 4, 5, 3, 6},
{8, 3, 4, 4, 5, 2},
{8, 3, 4, 2, 6, 2},
//code skips... ...
}
(The Array is not sorted)
I want to get all the "4" position, instead of searching the array one by one, and return the position, how can I search it faster / more efficient? thz in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
你不能。没有什么神奇的方法。您的算法始终需要检查矩阵中的每个单元格，因此对于大小为
n * m的矩阵，其始终为O(n*m)。如果您可以先对矩阵进行排序，那么您就可以摆脱
O(log(n) * m)的麻烦，因为您可以在每一行中使用二分搜索。You can't. There is no magic way. Your algorithm will always need to check each cell in your matrix, so it will always be
O(n*m)for a matrix of sizen * m.If you can sort your matrix first, then you can get away with
O(log(n) * m), as you can use a binary search inside each row.小于
m * n的唯一方法是以某种方式对其进行预排序。从你的问题中尚不清楚这是否可能。The only way to do this is less than
m * nis to have it presorted in some way. It is not clear from your question if that is possible.没有明显的算法优化（除非您对数据有一些先验知识，例如数据已排序，或者您知道有多少个 4）。然而，您可以使用一些微优化，例如，如果您的数组是 32 位 int 并且您可以使用 SSE，那么您可以一次加载和比较 4 个元素。
There is no obvious algorithmic optimisation (unless you have some a priori knowledge of the data, e.g. that it's sorted, or you know how many 4s there are). However there are micro-optimisations that you can use, e.g. if your array is 32 bit int and you can use SSE then you can load and compare 4 elements at a time.
您可以选择速度或内存消耗。如果内存不重要，您可以创建存储值的位置列表。所以你仍然有你的 m*n 数组，但还有一个“位置列表”数组。您必须创建“setter”方法，在每次添加或更改值时记下列表中的位置。因此，我们的想法不是改进搜索，而是避免搜索。
示例：
您有一个 2*2 数组。
并且您想在 中添加 4。因此，您必须调用 write 方法，该方法是使用参数 X、Y 和 Value 调用的。此方法会将您的数组更改为，
但也会创建一个
位置为四的列表。如果你添加第二个 4，它看起来像
所以如果你想在矩阵中找到所有 4，你只需要转到 List4 中的所有位置。当然，您必须为数组中的每个值创建一个列表。因此，如果矩阵仅包含每个值一次，则最多可以有 m*n 个包含位置的列表。
You can choose speed or memory consumption. If Memory is not important you could create a List of positions where values are stored. So you have still your m*n array, but additionaly an array of "position-lists". You would have to create "setter"-methods which write down a position in the lists each time a value is added or changed. So the idea is not to improve the search but avoid it.
Example:
You have a 2*2 Array.
And you want to add a 4 in the . So you have to call your method write which is called with the parameters X, Y, and Value. This method would change your array to
but also create a list
with the position of fours. If you add a second 4 it would look like
So if you want to find all 4 in your matrix you just have to go to all positions in your List4. Of course you would have to create a list for each value in your array. So you could have a maximum of m*n lists with positions if the matrix contains each value only once.