Nox*_*oxi 1 c++ algorithm binary-search
我有一个有限数组,其元素只有-1,0或1.我想找到一个数字的第N次出现的索引(比如说0).
我可以遍历整个数组,但我正在寻找更快的方法.我可以考虑使用二进制搜索,但无法对算法进行建模.在这种情况下,如何进行二进制搜索？
如果没有至少一次O(N)预处理,就不能这样做.从信息理论的角度来看,你必须知道元素[0:k-1]才能知道元素[k]是否是你想要的元素.
如果您要多次进行此搜索,则可以对数组进行简单的线性传递,随时计算每个元素.将索引存储在二维数组中,因此您可以直接索引所需的任何事件.
例如,给定[-1 0 1 1 -1 -1 0 0 0 -1 1],您可以将其转换为3xN数组,idx
[[0 4 5 9]]
[[1 6 7 8]]
[[2 3 10]]
元素I的第N次出现idx[I+1][N-1].
在初始O(N)传递之后,使用O(N)空间查找O(1)时间.