algorithm - 手动删除 O(n) 中的重复项

Question

我需要删除列表中的所有重复项，但前提是列表 a 中的项目与列表 b 中的项目相同。这是我当前的代码，但在处理 10 万个项目时需要几天的时间，有没有一种快速的方法可以做到这一点？

感谢任何帮助。

  List<int> ind = new List<int>();
            List<int> used = new List<int>();
            for (int i = 0; i < a.Count; i++)
            {
                for (int j = 0; j < a.Count; j++)
                {
                    if (i != j&&!used.Contains(i))
                    {
                        if (a[j] == a[i] && b[i] == b[j])
                        {
                            ind.Add(j);
                            used.Add(j);
                        }
                    }
                }
            }
            List<string> s2 = new List<string>();
            List<string> a2 = new List<string>();
            for (int i = 0; i < a.Count; i++)
            {
                if (!ind.Contains(i))
                {
                    s2.Add(a[i]);
                    a2.Add(b[i]);
                }
            }

Answer 1

许多此类问题的关键是正确的数据结构。为避免重复，您需要使用 Sets，因为它们会自动删除重复项。

这是Java中的代码，我希望它在C#中也类似:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

class Duplicates
{
    static List<Integer> list1 = new ArrayList<>();
    static List<Integer> list2 = new ArrayList<>();

    static final int SIZE = 100_000;
    static final int MAX_VALUE = 1000_000;

    public static void main(String[] args)
    {
        // populate the lists with random values for testing
        Random r = new Random();
        for(int i=0; i<SIZE; i++)
        {
            list1.add(r.nextInt(MAX_VALUE));
            list2.add(r.nextInt(MAX_VALUE));
        }
        Set<Integer> set1 = new HashSet<>(list1);
        Set<Integer> set2 = new HashSet<>(list2);

        // items that are in both lists
        Set<Integer> intersection = new HashSet<>(set1);
        intersection.retainAll(set2);

        Set<Integer> notSeenYet = new HashSet<>(intersection);

        List<Integer> list1Unique = new ArrayList<Integer>();
        for(int n: list1)
        {
            if(intersection.contains(n)) // we may have to skip this one
            {
                if(notSeenYet.contains(n)) // no, don't skip, it's the first occurrence
                {
                    notSeenYet.remove(n);
                }
                else
                {
                    continue;
                }
            }
            list1Unique.add(n);
        }
        System.out.println("list 1 contains "+list1Unique.size()+" values after removing all duplicates that are also in list 2");

    }

} 

10 万个值只需不到一秒的时间。

输出

list 1 contains 99591 values after removing all duplicates that are also in list 2