算法拼图访谈

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出现三次,两次三次,三次三次).

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

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.

准备两个哈希值,将每一行映射到它出现的第一个索引以及它出现的最后一个索引.通过键迭代并使用最后一个键 - 最后一个键.

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.子列表是第10个的第(1 + 1)个元素.

这是因为子列表是平衡的,当且仅当它的第一个和最后一个非标准化的直方图是相同的,直到添加一个常量,当且仅当第一个和最后一个标准化直方图相同时才会出现.

Answer 2

如果内存使用不重要,那很简单......

可以给矩阵尺寸N*p和保存在列(I)对应于多少个元素的值p之间寻找(ⅰ)在第二矢量的第一元素...

完成矩阵后,您可以搜索列中列i中的所有元素i没有不同的列.i答案是最大的.