47

我找到了这个面试问题，我想不出比 O(N^2 * P) 更好的算法：

给定一个 P 个自然数 (1,2,3,...,P) 的向量和另一个长度为 N 的向量，其元素来自第一个向量，找到第二个向量中最长的子序列，使得所有元素均匀分布（具有相同的频率）。

示例：(1,2,3) 和 (1, 2,1,3,2,1,3,1,2,3 ,1)。最长的子序列在区间 [2,10] 中，因为它包含第一个序列中频率相同的所有元素（1 出现 3 次，2 出现 3 次，3 出现 3 次）。

时间复杂度应该是 O(N * P)。

4

5 回答 5

49

“子序列”通常意味着不连续。我将假设您的意思是“子列表”。

这是一个 O(NP) 算法，假设我们可以散列（不需要假设；我们可以改为基数排序）。扫描数组，为每个数字保留一个运行总计。对于你的例子，

  1  2  3
 --------
  0  0  0
1 
  1  0  0
2
  1  1  0
1
  2  1  0
3
  2  1  1
2
  2  2  1
1
  3  2  1
3
  3  2  2
1
  4  2  2
2
  4  3  2
3
  4  3  3
1
  5  3  3

现在，通过减去最小元素来标准化每一行。结果是

 0: 000
 1: 100
 2: 110
 3: 210
 4: 100
 5: 110
 6: 210
 7: 100
 8: 200
 9: 210
10: 100
11: 200.

准备两个哈希，将每一行映射到它出现的第一个索引和它出现的最后一个索引。遍历键并取最后一个最大的键 - 首先。

000: first is at 0, last is at 0
100: first is at 1, last is at 10
110: first is at 2, last is at 5
210: first is at 3, last is at 9
200: first is at 8, last is at 11

最佳键是 100，因为它的子列表长度为 9。子列表是第 (1+1) 个元素到第 10 个元素。

这是因为当且仅当它的第一个和最后一个非标准化直方图相同直到添加一个常数时，子列表才是平衡的，当且仅当第一个和最后一个标准化直方图相同时才会发生这种情况。

于 2012-04-17T14:09:46.410 回答
6

如果内存使用不重要，那很容易......

您可以给出矩阵维度并在(i)N*p列中保存与在(i)第二个向量中的第一个元素之间查看的元素数量相对应的值...p

完成矩阵后，您可以搜索列i中所有元素i都不不同的列。最大i的就是答案。

于 2012-04-17T14:21:09.667 回答
3

通过随机化，您可以将其归结为线性时间。这个想法是用一个随机整数替换每个 P 值，使得这些整数总和为零。现在寻找两个相等的前缀和。这允许一些误报的可能性很小，我们可以通过检查我们的输出来补救。

在 Python 2.7 中：

# input:
vec1 = [1, 2, 3]
P = len(vec1)
vec2 = [1, 2, 1, 3, 2, 1, 3, 1, 2, 3, 1]
N = len(vec2)
# Choose big enough integer B.  For each k in vec1, choose
# a random mod-B remainder r[k], so their mod-B sum is 0.
# Any P-1 of these remainders are independent.
import random
B = N*N*N
r = dict((k, random.randint(0,B-1)) for k in vec1)
s = sum(r.values())%B
r[vec1[0]] = (r[vec1[0]]+B-s)%B
assert sum(r.values())%B == 0
# For 0<=i<=N, let vec3[i] be mod-B sum of r[vec2[j]], for j<i.
vec3 = [0] * (N+1)
for i in range(1,N+1):
    vec3[i] = (vec3[i-1] + r[vec2[i-1]]) % B
# Find pair (i,j) so vec3[i]==vec3[j], and j-i is as large as possible.
# This is either a solution (subsequence vec2[i:j] is uniform) or a false
# positive.  The expected number of false positives is < N*N/(2*B) < 1/N.
(i, j)=(0, 0)
first = {}
for k in range(N+1):
    v = vec3[k]
    if v in first:
        if k-first[v] > j-i:
            (i, j) = (first[v], k)
    else:
        first[v] = k
# output:
print "Found subsequence from", i, "(inclusive) to", j, "(exclusive):"
print vec2[i:j]
print "This is either uniform, or rarely, it is a false positive."
于 2012-04-19T05:14:07.090 回答
2

这是一个观察：你不能得到一个P长度不是乘法的均匀分布的序列。这意味着您只需检查, , ... long 的子序列 -N这样的序列。P2P3P(N/P)^2

于 2012-04-17T14:18:33.243 回答
0

您可以通过增强 uty 的解决方案将其降低到 O(N) 时间，而不依赖于 P。

对于每一行，不是存储每个元素的规范化计数，而是存储规范化计数的哈希，同时仅保留当前索引的规范化计数。在每次迭代期间，您需要首先更新归一化计数，如果计数的每次递减在递增时支付，则其摊销成本为 O(1)。接下来，您重新计算哈希。这里的关键是散列需要在被散列的元组元素之一的递增或递减之后轻松更新。

在这个问题的答案中显示了至少一种有效地进行这种散列的方法，并具有良好的理论独立性保证。请注意，计算指数以确定要添加到哈希的数量的 O(lg P) 成本可以通过预先计算以素数为模的指数来消除，预计算的总运行时间为 O(P)，给出总O(N + P) = O(N) 的运行时间。

于 2012-04-25T21:35:18.740 回答