列表交集

Question

我想计算一个列表“交集”。问题是：

L1 = [1, 0, 2, 3, 1 , 3, 0, 5]
L2 = [3, 5]

那么结果将是

L3 = [0, 0, 0, 1, 0, 1, 0, 1]

然后我将把这个结果转换为一个字节。在本例中，十进制格式为 21。

我想在delphi 中制作，并且我需要高效地完成此操作。有没有比 O(m*n) 更好的方法来解决这个问题？

Answer 1

这是一个应该可以完成您想要的功能的函数。我将 L2 定义为一个集合而不是数组，因为您说过所有值都适合一个 Byte。其复杂度为O(n)；检查集成员资格以恒定时间运行。但由于结果需要容纳一个字节，L1 的长度必须限制为 8，因此该函数的复杂度实际上是 O(1)。

function ArrayMembersInSet(const L1: array of Byte; const L2: set of Byte): Byte;
var
  i: Integer;
  b: Byte;
begin
  Assert(Length(L1) <= 8,
    'List is to long to fit in result');
  Result := 0;
  for i := 0 to High(L1) do begin
    b := L1[i];
    if b in L2 then
      Result := Result or (1 shl (7 - i));
  end;
end;

Answer 2

罗布的答案适用于这个具体案例。对于必须比较两个列表的更一般情况，如果两个列表都已排序，则可以在 O(m+n) 时间内完成。 （或者如果你必须先对它们进行排序，则需要 O(n log n) 时间，但这仍然比 O(m*n) 快得多。）

基本的列表比较算法如下所示：

procedure ListCompare(list1, list2: TWhateverList; [Add extra params here]);
var
  i, j: integer;
begin
  i := 0;
  j := 0;
  while (i < list1.Count) and (j < list2.Count) do
  begin
    if list1[i] < list2[j] then
    begin
      //handle this appropriately
      inc(i);
    end
    else if list1[i] > list2[j] then
    begin
      //handle this appropriately
      inc(j);
    end
    else //both elements are equal
    begin
      //handle this appropriately
      inc(i);
      inc(j);
    end;
  end;

  //optional cleanup, if needed:
  while (i < list1.Count) do
  begin
    //handle this appropriately
    inc(i);
  end;
  while (j < list2.Count) do
  begin
    //handle this appropriately
    inc(j);
  end;
end;

这可以为一大堆进行定制任务，包括列表交集，通过更改“适当处理这个”位置，并且保证不会运行比两个列表中加在一起的步骤更多的步骤。对于列表交集，让 equals 情况将值添加到某些输出，另外两个除了推进计数器之外什么也不做，并且您可以省略可选的清理。

使用此算法的一种方法是将顶部的额外参数设置为函数指针，并传入将处理适当情况的例程，或者传递 nil 不执行任何操作。 （如果你走这条路，请确保在调用它们之前检查 nil ！）这样你只需要编写一次基本代码。

Answer 3

无论如何，您都需要访问每个列表中的每个元素来比较值。嵌套循环将在 O(n^2) 内完成此操作，并且转换应该只是本地工作。

编辑：我注意到你想要比 O(n*m) 更好的运行时间。