Проверьте два списка <int> для тех же номеров

Ответ 1

Вы можете использовать метод расширения .net 3.5.Intersect(): -

List<int> a = new List<int>() { 1, 2, 3, 4, 5 };
List<int> b = new List<int>() { 0, 4, 8, 12 };

List<int> common = a.Intersect(b).ToList();

Ответ 2

Джефф Рихтер отлично подходит для PowerCollections с перекрестками. Работает полностью на .NET 2.0.

http://www.codeplex.com/PowerCollections

        Set<int> set1 = new Set<int>(new[]{1,2,3,4,5});
    Set<int> set2 = new Set<int>(new[]{0,4,8,12});
    Set<int> set3 = set1.Intersection(set2);

Ответ 3

Вы можете сделать это так, как это делает LINQ, эффективно - с помощью набора. Теперь до 3.5 мы не получили правильный тип набора, поэтому вам нужно использовать Dictionary<int,int> или что-то вроде этого:

• Создайте Dictionary<int, int> и заполните его из списка a, используя этот элемент как ключ и значение для записи. (Значение в записи действительно не имеет значения.)
• Создайте новый список для пересечений (или напишите это как блок итератора, что угодно).
• Перейдите по списку b и проверьте со словарем. ContainsKey: если это так, добавьте запись в список или выпустите ее.

Это должно быть O (N + M) (т.е. линейное в обоих размерах списка)

Обратите внимание, что это даст вам повторяющиеся записи, если список b содержит дубликаты. Если вы хотите этого избежать, вы всегда можете изменить значение словаря, когда вы впервые увидите его в списке b.

Ответ 4

Вы можете отсортировать второй список и выполнить цикл через первый, и для каждого значения выполнить двоичный поиск на втором.

Ответ 5

Если оба списка отсортированы, вы можете легко сделать это в O (n) раз, выполнив модифицированное слияние из merge-sort, просто "удалите" (шаг за шагом) нижнего из двух ведущих чисел, если они всегда равны, сохраняют это число в списке результатов и "удаляют" оба из них. он занимает меньше n (1) + n (2) шагов. Это, конечно, предполагает, что они отсортированы. Но сортировка целых массивов не совсем дорога O (n log (n))... Я думаю. Если вы хотите, чтобы я мог скомпоновать некоторый код о том, как это сделать, но идея довольно проста.

Ответ 6

В комментарии к вопросу автор сказал, что будет

Максимум 15 в первом списке и 20 в второй список

В этом случае я не буду беспокоиться об оптимизации и использовать List.Contains.

Для больших хэшей списков можно использовать поиск O (1), который приводит к алгоритму O (N + M), как отметил Джон.

Для Hash требуется дополнительное пространство. Чтобы уменьшить использование памяти, мы должны иметь самый короткий список.

List<int> a = new List<int>() { 1, 2, 3, 4, 5 };
List<int> b = new List<int>() { 0, 4, 8, 12 };
List<int> shortestList;
List<int> longestList;
if (a.Count > b.Count)
{
    shortestList = b;
    longestList = a;
}
else
{
    shortestList = a;
    longestList = b;                
}

Dictionary<int, bool> dict = new Dictionary<int, bool>();
shortestList.ForEach(x => dict.Add(x, true));

foreach (int i in longestList)
{
    if (dict.ContainsKey(i))
    {
        Console.WriteLine(i);
    }
}

Ответ 7

Протестировано на 3.0

    List<int> a = new List<int>() { 1, 2, 3, 4, 5, 12, 13 };
    List<int> b = new List<int>() { 0, 4, 8, 12 };
    List<int> intersection = new List<int>();
    Dictionary<int, int> dictionary = new Dictionary<int, int>();
    a.ForEach(x => { if(!dictionary.ContainsKey(x))dictionary.Add(x, 0); });
    b.ForEach(x => { if(dictionary.ContainsKey(x)) dictionary[x]++; });
    foreach(var item in dictionary)
    {
        if(item.Value > 0)
            intersection.Add(item.Key);
    }

Ответ 8

var c = a.Intersect(b);

Это работает только в 3.5, и я видел ваши требования в своих приложениях.

Ответ 9

Метод, рекомендованный ocdecio, является хорошим, если вы собираетесь реализовать его с нуля. Рассматривая временную сложность по сравнению с методом nieve, мы видим:

Метод сортировки/двоичного поиска: T ~ = O (n log n) + O (n) * O (log n) ~ = O (n log n)

Цитирование через оба списка (метод nieve): T ~ = O (n) * O (n) ~ = O (n ^ 2)

Может быть более быстрый метод, но я не знаю об этом. Надеюсь, это должно оправдать выбор его метода.

Ответ 10

Вот метод, который удаляет повторяющиеся строки. Измените это, чтобы принять int, и он будет работать нормально.

public List<string> removeDuplicates(List<string> inputList)
    {
        Dictionary<string, int> uniqueStore = new Dictionary<string, int>();
        List<string> finalList = new List<string>();

        foreach (string currValue in inputList)
        {
            if (!uniqueStore.ContainsKey(currValue))
            {
                uniqueStore.Add(currValue, 0);
                finalList.Add(currValue);
            }
        }
        return finalList;

    }

Обновление: Извините, я фактически совмещаю списки и удаляю дубликаты. Я передаю объединенный список этому методу. Не совсем то, что вы ищете.

Ответ 11

(Предыдущий ответ - изменил IndexOf на Contains, так как IndexOf сначала переходит к массиву)

Увидев, что это два небольших списка, код ниже должен быть в порядке. Не уверен, есть ли библиотека с таким способом пересечения, как Java (хотя List не является набором, поэтому он не работает), я знаю, как кто-то указал, что в библиотеке PowerCollection есть один.

List<int> a = new List<int>() {1, 2, 3, 4, 5};
List<int> b = new List<int>() {0, 4, 8, 12};

List<int> result = new List<int>();
for (int i=0;i < a.Count;i++)
{
    if (b.Contains(a[i]))
        result.Add(a[i]);
}

foreach (int i in result)
    Console.WriteLine(i);

Обновление 2: HashSet был немым ответом, так как он не 3,5

Обновить: HashSet кажется очевидным:

// Method 2 - HashSet from System.Core
HashSet<int> aSet = new HashSet<int>(a);
HashSet<int> bSet = new HashSet<int>(b);
aSet.IntersectWith(bSet);
foreach (int i in aSet)
    Console.WriteLine(i);

Ответ 12

Ого. Ответы до сих пор выглядят очень сложными. Почему бы просто не использовать:

List<int> a = new List<int>() { 1, 2, 3, 4, 5, 12, 13 };
List<int> b = new List<int>() { 0, 4, 8, 12 };

...

public List<int> Dups(List<int> a, List<int> b)
{
    List<int> ret = new List<int>();

    foreach (int x in b)
    { 
        if (a.Contains(x))
        {
           ret.add(x);
        }
    }

    return ret;
}

код >

Это кажется гораздо более прямолинейным для меня... если я не пропустил часть вопроса. Это вполне возможно.