我有一个有限数组，其元素只有 -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(1)，使用 O(N) 空间。
关于c++ - 使用二进制搜索查找数字第 N 次出现的索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48198472/