2

如果我有两个数组。例如，一个数组是int[] one={1,2,4,6,54,3,34};另一个数组int[] two={12,1,2,4,7,8,54,3,34,5}; 。问题是如何在一个和两个之间获得“相同的部分”。示例中的“相同部分”是 [1,2,4] 和 [54,3,34]。

PS您可以使用伪语言、c、c#、java、php 或其他语言。

PS现在我明确了相同的部分。相同的部分元素具有列表。

PSI 更改了示例，并且数组中每个项目的值不相等（您可以查看我的示例。）

  1. 至少有两个项目匹配
  2. 两个数组中匹配项的索引不一定要匹配，但相同的部分必须是连续的。
4

3 回答 3

1

您可以为两个数组（视为“字符串”）构建后缀树并比较两个树。

特别是，您可以选择两棵树中的一棵（例如，与较小数组关联的那棵）（称为 A）并开始遍历它，模仿另一棵树上的移动（称为 B）。

如果您在树 A 的节点 u 中，并且您无法从该节点复制任何“移动”到树 B 的相应节点，那么您找到了“最大匹配”（从根到 u 拼写的那个）您可以修剪以 u 为根的树 A 的子树。

这只是一个想法，你必须建立在它之上；请注意，您可以在 O(n) 中构建后缀树，这种“双相似性”也是 O(n)，因此看起来是最优的。

于 2011-04-30T17:05:09.443 回答
0

几乎是蛮力的一些优化。最坏情况 O(n^4)。n 是较短数组的大小。

one=[1,2,4,6,54,3,34]
two=[12,2,4,3,54,3,5]
one_pos_list_map = {}  # map of value -> position list
one_pos_map = {}  # map of value -> map of position -> 1
for pos in xrange(len(one)):
  val = one[pos]
  if val not in one_pos_map:
    one_pos_map[val] = {}
  one_pos_map[val][pos] = 1 
  if val not in one_pos_list_map:
    one_pos_list_map[val] = []
  one_pos_list_map[val].append(pos)

checked = [False for i in xrange(len(two)*len(two))] 
def print_maximal_matches(start, end):
  idx = start * len(two) + end - 1 
  if (checked[idx] or end - start < 2): 
    return
  checked[idx] = True
  match_pos_list = one_pos_list_map.get(two[start], [])
  for match_pos in match_pos_list:
    found = True
    for i in xrange(start + 1, end): 
      if not one_pos_map.get(two[i], {}).get(match_pos + i - start, None):
        found = False
        break
    if found:
      print two[start:end]
      return

  print_maximal_matches(start + 1, end)
  print_maximal_matches(start, end - 1)

print_maximal_matches(0, len(two))
于 2011-04-30T17:59:02.553 回答
0

这可能是最长的公共子序列问题。

于 2011-04-30T16:17:17.553 回答