在给定的 （+ve） 整数数组中查找任何元素的频率

这需要在分析数组时销毁数组。

我们将在一次传递中评估这些值。我们将使用数组中的第一个作为 Cuckoo 哈希来做到这一点，如下所示。n/76n/7

1. 我们将该部分划分为成对的元素。
2. 如果给定的货币对具有 那么 不是一个值，那就是一个空桶。(i,j)j <= nj
3. 如果给定的货币对不在哈希值中将要进入的 2 个位置之一，则这是一个空桶。(i,j)j
4. 假设它是一个完整的存储桶，如果 ，则在哈希中出现一次。n < ij
5. 假设它是一个完整的存储桶，如果 ，则出现在哈希时间中。n <= iji

请注意，数组中的第一个将被视为桶，它是我们尝试散列的值的 3 倍。因此，我们的负载系数是 Cuckoo 哈希有效。6n/73n/7n/71/3 < 1/2

我将从这里概述它。但这就是这个想法。

我们需要一个计数器来计算哈希中有多少个不同的值。inserted_values

我们通过扫描哈希桶进行初始化，以查看有多少哈希桶恰好在正确的位置具有一个值，从而成为完整的桶。请注意，如果一个值出现在两个地方，它可能是正确的，那么只有第一个哈希值的值是正确的。inserted_values

现在我们从阵列的末尾开始，向前面移动。当我们查看每个值时，我们按如下方式进行。

idx = len(array)
while 0 < idx:
    idx -= 1
    current_value = array[idx]
    if current_value is <= n:
        pass
    elif current_value is correctly placed in the hash:
        pass
    elif current_value can be found in the hash:
        if current_value only appears once:
            swap where count will go with where current_value is
            set count to 2
            idx += 1
        else:
            increment count
            set current_value to 0
    elif inserted_values < n/7:
        swap current value with where it belongs in the hash
        counter += 1

（注意：我省略了重新散列。这增加了相当大的复杂性，但原理是一样的。

现在我们可以扫描哈希桶，以查找值及其计数。如果有人有符合您条件的计数，您就有答案。否则为 0，则输出计数和处理的值。n/7

每个阶段处理哈希，所以最多需要 7 个。每个需要 2 次通过，因此总共需要 14 次通过。这是工作（我在重新散列时留下了一些复杂性，所以让我们说很有可能的工作）来产生你的答案。n/7O(n)O(n)

它使用数组本身来跟踪所有内容。此外，您还需要内存，因此它符合规定的要求。O(1)