快速查找字符串列表中的重复项

Question

什么是在Tstringlist中查找重复项的最快方法.我获得了在Stringlist中搜索重复项所需的数据.我目前的想法是这样的:

    var  TestStringList, DataStringList  : TstringList;


    for i := 0 to  DataStringList.Items-1 do
    begin
        if TestStringList.Indexof(DataStringList[i])< 0 < 0 then
        begin
          TestStringList.Add(DataStringList[i])
        end
        else
        begin
           memo1.ines.add('duplicate item found');
        end;

    end;
   ....

Answer 1

只是为了完整性,(并且因为你的代码实际上没有使用副本,只是表明已找到一个副本):Delphi TStringList具有内置的处理重复条目的能力,在它的Duplicates属性中.将其设置为dupIgnore只会丢弃您尝试添加的任何重复项.请注意,目标列表必须排序,或Duplicates无效.

TestStringList.Sorted := True;
TestStringList.Duplicates := dupIgnore;

for i := 0 to  DataStringList.Items-1 do
   TestStringList.Add(DataStringList[i]);
Memo1.Lines.Add(Format('%d duplicates discarded',
                      [DataStringList.Count - TestStringList.Count]));

快速测试表明,如果您使用Sorted和,可以删除整个循环Duplicates:

TestStringList.Sorted := True;
TestStringList.Duplicates := dupIgnore;

TestStringList.AddStrings(DataStringList);
Memo1.Lines.Add(Format('%d duplicates discarded',
                      [DataStringList.Count - TestStringList.Count]));

有关TStringList.Duplicates详细信息,请参阅文档.

Answer 2

我认为你正在寻找重复.如果是,那么您执行以下操作:

案例1:字符串列表已订购

在这种情况下,重复项必须出现在相邻的索引处.在这种情况下,您只需从环1到Count-1,并检查是否索引的内容i是一样的,在指数i-1.

案例2:未订购字符串列表

在这种情况下,我们需要一个双循环.它看起来像这样:

for i := 0 to List.Count-1 do
  for j := i+1 to List.Count-1 do
    if List[i]=List[j] then
      // duplicate found

有性能方面的考虑.如果列表是有序的,则搜索是O(N).如果未对列表进行排序,则搜索为O(N ²).显然前者更可取.由于列表可以按复杂度O(N log N)进行排序,如果性能成为一个因素,那么在搜索重复项之前对列表进行排序将是有利的.