algorithm - 数组中的元素数大于给定数

Question

好的，所以我知道这个问题已经被问过无数次了，因为我用谷歌搜索了各种可能的形式，但没有得到答案。

我有一个数组说 A= {10, 9, 6, 11, 22 }。我必须找到大于 11 的元素数。

我知道这可以使用改进的二进制搜索来完成，但我需要在 O(1) 时间内完成。这可能吗？

(请记住，我们将元素作为输入，因此在获取输入时可能会进行一些预计算。)

Answer 1

1. 从数组中删除所有的 0 并计算它们。现在您知道输入 0 的结果:n - 计数。然后从数组中的所有剩余元素中减去 1。此步骤的目标是将数字置于 [0,999999999] 范围内。如果输入大于 0，也从中减一，否则立即返回结果。

2. 对数字进行排序并将它们视为 9 位数字的字符串(用前导 0 填充)。

3. 构建树。每个节点代表一个数字。每个叶子都必须存储大于自身的数字数量。我认为节点数不会太高。对于最大 n = 10^5，我们可以获得大约 5*10^5 个节点(10^5 个不同的前缀使我们下降到大约 5 级之后，我们必须有链表到叶子 10^5 existing + 4*10 ^5 用于链表)。

4. 现在您必须遍历所有非叶节点，并为子节点中所有缺失的数字创建指向下一个较小叶节点的直接链接。如果您将链接表示为与下一个较低叶子具有相同计数的叶子，则大约额外 9*4*10^5 个节点。

5. 我认为现在理论上您可以得到 O(1)，因为请求的复杂性不依赖于 n 并且您将比创建 HashMap 时节省更少。对于最坏的情况，你必须下降 9 个节点，这是一个独立于 n 的常数。