列表交集

| 我想计算一个列表“交叉点”。问题是:
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)更好地解决此问题的方法?     
已邀请:
这是应该执行您想要的功能。我将
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;
    
罗伯的答案将适用于此特定情况。对于必须比较两个列表的更一般的情况,如果两个列表都已排序,则可以在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;
可以通过更改“适当地处理此”位置为一整套任务(包括列表交集)进行自定义,并且保证运行的步骤不会超过两个列表的总和。对于列表交集,在等号的情况下将值添加到某些输出中,而其他两个则除了增加计数器外什么都不做,您可以省略可选的清除操作。 使用此算法的一种方法是使顶部的多余参数成为函数指针,并传入可处理适当情况的例程,或者不执行任何操作则为nil。 (只要走那条路,确保在调用nil之前先检查nil!)这样,您只需编写一次基本代码即可。     
好吧,无论您需要访问哪个列表中的每个元素来比较这些值,都是如此。嵌套循环将在O(n ^ 2)中完成此操作,并且转换应仅是本地工作。 编辑:我注意到您想要一个比O(n * m)更好的运行时。     

要回复问题请先登录注册