使用哈希算法统计整数数组中模式出现的次数。

Question

使用哈希算法统计整数数组中模式出现的次数。

3

我有一个问题，我有一个整数数组，我定义一个区间是好的区间当且仅当在该区间内每个整数出现的次数都是偶数(包括零)。我想找到给定整数数组中好的区间的数量。例如，如果数组=[7,7,1,5,5,1]，那么好的区间分别为[1,2]、[3,6]、[4,5]、[1,6]，对应连续子数组 [7,7]、[1,5,5,1]、[5,5]、[7,7,1,5,5,1]。如果数组=[4,5,6,5,4]，则没有好的区间。

我有一个朴素的解决方案，就是使用两个for循环并检查每个可能的区间是否存在好的区间，但这需要O(n^2)的时间。我想找到一个更好的解决方案，能够在O(nlogn)的时间内运行，并且我认为使用哈希可以给我一个更快的解决方案，问题是我不知道如何将它纳入我的答案。我一直在阅读滚动 Robin-Karp 哈希算法来给我一些思路，但我认为这个算法不适用于我所寻求的。你们有没有任何使用哈希解决此问题的O(nlogn)时间复杂度算法的想法呢？

- ISeekTheWisdom

2个回答

0

运行时间：O(n * r)，其中n是输入数组的大小，r是不同元素的数量。在最坏情况下，r接近于n，这是O(n^2)。

假设：您的整数是连续的或至少很小。如果您有比不同整数数量大得多的整数，则应使用哈希为每个整数分配唯一的ID：0、1、2、...，并将我的算法应用于这些ID。

初始化以下内容：

bitvec = 0。我们将使用它来跟踪解析输入数组时我们已经看到每个元素的次数的奇偶性。

bitvec_to_count：一个哈希表，每个新键的起始值为零，并将跟踪我们已经看到每个bitvec的次数。

设置bitvec_to_count [0] = 1。我们使用它来表示我们已经看到了表示没有元素的bitvec一次。

现在解析数组。对于数组的第i个元素，翻转bitvector的第i位（因为该元素的奇偶性已更改）。增加此bitvector的计数。

最后，对于bitvec_to_count哈希表中所有计数（值），取choose(count, 2)的总和。这就是你的答案。

这利用了一个事实，即好的间隔恰好是在开始前和结束时元素的奇偶性相同（因为间隔本身的元素的奇偶性都是零，因为它们都出现了偶数次）。

这是工作中的Ruby代码；应该很容易转换成Python。

def f(arr)
  bitvec = 0
  bitvec_to_count = Hash.new{|h, k| h[k] = 0}
  bitvec_to_count[bitvec] += 1
  
  arr.each do |val|
    bitvec ^= 1 << val
    bitvec_to_count[bitvec] += 1
  end
  
  ans = 0
  
  bitvec_to_count.values.each do |count|
    ans += count * (count - 1) / 2 
  end
  
  return ans
end

- Dave

1

我认为这并不是真正的线性，因为你依赖于对n个O(n)位整数的操作是O(1)。你能在一个包含一百万个不同整数的输入列表上运行你的代码吗？一千万个呢？ - Paul Hankin

@PaulHankin 没错！+1。我会更新运行时间。 - Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

假设您的数组名为A。

对于每个索引i，您可以计算出在A [: i]中出现奇数次的元素集合。现在，您的问题等同于找到所有i，j，使得这些集合相等。

在最坏情况下，这仍然是O（n ^ 2），但是您可以使用这些集合的哈希值而不是使用集合本身。为了提高效率，哈希值需要从先前集合的哈希值增量计算。一种方法是使用集合元素的通用哈希函数的XOR。使用此方法，您可以在O（1）时间内添加和删除单个元素，并且它具有添加和删除元素完全相同的操作，非常适合此问题，其中重要的是元素的奇偶性而不是确切数量。

因此，为0到n的索引计算此新数组，包括n。

B[0] = 0
B[i+1] = HASH(A[i]) XOR B[i]

然后计算所有0<=i

这是一种概率上正确的算法，因为如果你运气不好，一个非空集合可能具有零哈希。如果您使用通用的b位哈希，其正确的概率的上限大约是exp(-n²/2^(b+1)) -- 从生日问题概率得出。因此，如果您使用128位哈希，在实践中找到的任何输入都是相当安全的。

以下是Python代码示例，它实现了使用集合的朴素版本，在最坏情况下运行时间为O(n^2)。

import collections

def naive_evens(A):
    B = frozenset()
    counts = collections.Counter()
    counts[B] += 1
    total = 0
    for a in A:
        B = B.symmetric_difference({a})
        total += counts[B]
        counts[B] += 1
    return total

以下是使用哈希实现的概率上正确且时间复杂度为 O(n) 的版本。它使用 HASH 作为通用哈希函数（随机种子为 HA），并使用参数 HW 和 HM 来描述单词大小和要创建的哈希位数。为了避免将 0 哈希到 0，数组元素被修改为全为正数（通过添加某些元素使得最小元素始终为 1）。

import collections
import random

HW = 256
HM = 128
HA = random.randrange(1 << HW)

def HASH(x):
    h = (HA * x) % (1 << HW)
    return h >> (HW - HM)

def smart_evens(A):
    B = 0
    counts = collections.Counter()
    counts[B] += 1
    total = 0
    M = min(A)
    for x in A:
        B = B ^ HASH(x - M + 1)
        total += counts[B]
        counts[B] += 1
    return total