2

有没有办法提取集合中的最高（或最低）值？例如，如果我有以下“字节集”：

[0, 1, 2, 4, 5, 28, 199]

有什么功能我可以在上面运行并返回 199 作为结果？

编辑：有一个明显的暴力解决方案涉及 for..in 循环。如果可能的话，我想找到比这更好的方法。

4

5 回答 5

15

循环确实是正式正确的方法。

type
  TSetType = set of TEnumType;

function HighestMember(const s: TSetType): TEnumType;
begin
  for Result := High(Result) downto Low(Result) do
    if Result in s then
      exit;
  raise Exception.Create('empty sets have no highest member');
end;

任何其他类型的解决方案都需要类型转换或汇编程序，这两者都会迫使您失去类型安全性——可以说，它们是“语言之外的”。

如果你能保证你的集合不超过32个可能的元素，那么这个集合可以用一个普通的整数覆盖，你的问题就相当于询问一个32位整数中最高位集合的位置。之前在这里被问过，差不多：

如果您对集合类型没有 32 个元素的限制，那么您有 Delphi 的 256 个元素的限制，并且任何位旋转解决方案都需要处理 32字节的输入。

于 2009-05-06T23:28:47.813 回答
6

集合是无序的，所以你不会比循环更好。如果您经常查找集合的最小/最大值，请使用堆数据结构，它提供 O(1) 查找来获取最小/最大值和 O(log n) 查找任何其他值。

于 2009-05-07T00:03:01.660 回答
2

这是一个更快的版本，它使用了字节集内部结构的知识。

type
  TByteSet = set of Byte;

function HighestElement(const ByteSet: TByteSet): Byte;
type
  TSetBytes = array[0..SizeOf(TByteSet) - 1] of Byte;
var
  I, J: Integer;
  B: Byte;
  SetBytes: TSetBytes;
begin
  if ByteSet <> [] then
  begin
    SetBytes := TSetBytes(ByteSet);
    // Start at the top and work down, one byte at a time
    for I := SizeOf(TByteSet) - 1 downto 0 do
    begin
      // Any bits set here
      B := SetBytes[I];
      if B <> 0 then
      begin
        Result := I * 8;
        for J := 0 to 7 do
          if (B shr J) and 1 <> 0 then
          begin
            Result := Result + J;
            Exit;
          end;
      end;
    end;
  end else
    // No elements set
end;

您可以将集合的类型 TByteSet 更改为几乎任何集合类型，并且该函数应该仍然有效。只需将函数 decl 和 body 中的 TByteSet 替换为您的集合类型即可。如果使用一组 AnsiChar 或一组枚举类型，您还可以修改它以返回实际的元素类型。要获得最小值，请将 for 循环的“I”更改为“0 to SizeOf(TByteSet) - 1”，并将“J”循环中的 if 测试更改为“if (B shl J) and $80 <> 0”

于 2009-05-07T16:29:44.333 回答
1

几乎相同，但更短：

type
  TByteSet = set of Byte;

function MaxSet(S: TByteSet): Byte;
var
  CardArr: Array [0..7] of Cardinal absolute S;
  i: Byte;
begin
  i := 7;
  while (i > 0) AND (CardArr[i] = 0) do
    Dec(i);
  Result := i + Floor(Log2(CardArr[i]));
end;
于 2012-11-04T15:53:44.357 回答
1

最高和最低，不使用数学单位：

type
  TCharSet = set of Char;

function MaxOfSet(aSet: TCharSet):Char;
var
  Data:array[0..SizeOf(TCharSet)-1] of Byte absolute aSet;
  i,r:Byte;
begin
  if aSet<>[] then begin
     i:=SizeOf(TCharSet)-1;
     while (i>0) and (Data[i]=0) do
        Dec(i);
     r:=i*8;
     i:=Data[i];
     while (i and $80)=0 do begin
        i:=i shl 1;
        Dec(r)
     end;
     Result:=Chr(r+7)
  end
  else
     raise Exception.Create('Unable to extract max value from an empty set');
end;

function MinOfSet(aSet: TCharSet):Char;
var
  Data:array[0..SizeOf(TCharSet)-1] of Byte absolute aSet;
  i,r:Byte;
begin
  if aSet<>[] then begin
     i:=0;
     while (i<SizeOf(TCharSet)-1) and (Data[i]=0) do
        Inc(i);
     r:=i*8;
     i:=Data[i];
     while (i and 1)=0 do begin
        i:=i shr 1;
        Inc(r)
     end;
     Result:=Chr(r)
  end
  else
     raise Exception.Create('Unable to extract min value from an empty set');
end;
于 2017-12-14T13:57:24.907 回答