列表相交 [英] List Intersection

问题描述

我想计算一个列表交集".问题是:

I want to compute a list "intersection". The problem is:

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

那么结果将是

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

然后我将把这个结果转换为一个字节.在这种情况下，十进制格式将为21.

Then i will convert this result in a byte. In this case will be 21 in decimal format.

我想用delphi制作，我需要高效地做.有没有比O(m * n)更好的解决这个问题的方法?

I want to make in delphi and I need this do efficiently. Is there a way to solve this problem better than O(m*n)?

推荐答案

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

Here's a function that should do what you want. I defined L2 as a set instead of an array since you said all your values will fit in a Byte. Its complexity is O(n); checking set membership runs in constant time. But since the result needs to fit in a byte, the length of L1 must be bound at 8, so the complexity of this function is actually 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;

这篇关于列表相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！