算法谜题面试

Question

我看到了这个面试题，但是我想不出比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出现了三次，2出现了三次，3出现了三次）。

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

- flowerpower

---

子序列是否必须是连续的？ - svick

是的，子序列 V[i..j] 由元素组成：V[i]、V[i+1]、...、V[j]。 - flowerpower

Answer 1

"子序列"通常表示非连续的。我会假设你的意思是"子列表"。

这里有一个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.

准备两个哈希表，将每一行映射到其第一次出现的索引和最后一次出现的索引。遍历键并选择具有最大last - first的键。

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个元素。

这是因为当且仅当子列表的第一个和最后一个未规范化的直方图在添加常量的情况下相同时，子列表是平衡的，这种情况只会发生在第一个和最后一个归一化直方图相同时。

- uty

---

在搜索每行的起始和结束位置的情况下，需要O(N^2)的时间来搜索N行。除此之外似乎工作正常。 - WeaselFox

哈希/基数排序的整个意义在于我们不必搜索平方级别的可能性。 - uty

@WeaselFox：你可以只需遍历列表一次，对于每个条目检查代码（例如：200），如果是新代码，则将索引设置为第一个和最后一个，否则仅设置为最后一个。你还可以存储当前的最大最小值，因此在迭代结束时，你就有了解决方案。实际上，你甚至不必存储最后一个索引。 - Karoly Horvath

在更高的层面上，我正在通过它们对应的归一化行来分区索引。这最容易通过哈希解释，但由于每个条目都在0到N之间，我们可以在O（NP）时间内对索引进行基数排序，然后仅通过比较已排序顺序中相邻元素来进行分区。 - uty

@Downvoter 抱歉破坏了你喜欢的面试问题。(或者你是有正当的抱怨吗？) - uty

Answer 2

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

您可以给出矩阵的维度N*p，并在列(i)中保存相应值，该值对应于第二个向量中从(i)第一个元素开始查找p所需的元素数量。

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

- amin k

---

我认为Karoly的意思是 - 欢迎来到Stack Overflow，但你的回答不够清晰。 - dfb

不要担心，你需要做的就是更好地解释你的想法。举个例子，看看别人在说什么，然后尝试将你的解决方案与他们的联系起来——例如，听起来你的答案与上面的一个答案相似，所以你可能走在正确的道路上。利用你手头的工具，不要气馁。这需要一段时间才能适应这里的感觉。 - dfb

@amin k: 我加入这里的原因之一是为了提高我的英语水平。我知道第一次写出清晰易懂的文风有多么困难，尽力而为就好；) - Karoly Horvath

@KarolyHorvath：我还在这里，努力变得更好，你有什么想法？ - amin k

@dfb：我还在这里，努力变得更好，你有什么想法？ - amin k

Answer 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."

- mic

---

非常好的想法！不过，你的算法和uty的答案一样是O(N*P)，但它更节省空间。顺便说一下：如果你大多数情况下选择比N大的质数，你可以减少误报的可能性。不幸的是，其中一个替代品不能是质数，因为你需要总和为零。 - Hans-Peter Störr

Answer 4

这里有一个观察结果：你无法得到一个长度不是P的均匀分布序列。这意味着你只需要检查N的子序列，它们的长度为P，2P，3P... - 这样的序列总共有(N/P)^2个。

- WeaselFox

---

然后，如果你很聪明，你可以得到一个O(N^2/P)的解决方案...不幸的是，他需要更好的。 - Karoly Horvath

Answer 5

通过增强uty的解决方法，您可以将其缩短到O（N）时间，并且不依赖于P。

对于每一行，存储每个元素的归一化计数的哈希值，同时仅保留当前索引的归一化计数，而不是存储每个元素的归一化计数。在每次迭代中，您需要首先更新归一化计数，如果在增加计数时支付减少计数，则其摊销成本为O（1）。接下来重新计算哈希值。关键在于哈希值需要在哈希元组的一个元素被增加或减少后容易进行更新。

至少有一种有效且具有良好理论独立性保证的哈希方式，可以在this question的答案中找到。请注意，可以通过预先计算模质数的指数来消除计算指数以确定要添加到哈希值的数量的O（lg P）成本，并具有总运行时间为O（P）的预计算时间，从而获得总运行时间为O（N + P）= O（N）的结果。

- jonderry