Проверьте два Списка <интервал> на те же числа

Превосходный PowerCollections Jeff Richter Установил с Пересечениями. Работы полностью назад к.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);

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

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

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

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

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

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

Протестированный по телефону 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);
    }

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

Max 15 в первом списке, и 20 во втором списке

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

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

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

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);
    }
}

var c = a. Пересекитесь (b);

Это только работает в 3,5, видел Ваше требование мои извинения.

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

метод Вида/двоичного поиска: T ~ = O (n регистрируют n), + O (n) * O (регистрируют n), ~ = O (n регистрируют n)

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

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

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

Наблюдение, поскольку это - два маленьких списка, код ниже должен быть прекрасным. Не уверенный, если существует библиотека с перекрестным методом как Java, имеет (хотя Список не является набором, таким образом, она не работала бы), я знаю, поскольку кто-то указал, что библиотека 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 не 3.0

Обновление : 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);

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

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;

    }

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

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

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;
}

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