Сравните массивы int в высокой производительности

Question

Не могу вспомнить из моих дней в колледже, как сравнить два несортированных массива int и найти количество совпадений?Каждое значение уникально в своем собственном массиве, и оба массива имеют одинаковый размер.

например

int[5] a1 = new []{1,2,4,5,0}
int[5] a2 = new []{2,4,11,-6,7}

int numOfMatches = FindMatchesInPerformanceOfNLogN(a1,a2);

кто-нибудь помнит?

Answer 1

Один массив должен быть отсортирован, чтобы вы могли сравнить в n * log (n). То есть для каждого элемента в несортированном массиве (n) вы выполняете двоичный поиск по отсортированному массиву (log (n)). Если оба не отсортированы, я не вижу способа сравнить в n * log (n).

Answer 2

Если вы можете хранить содержимое одного из массивов в HashMap, то вы можете проверить наличие элементов в другом массиве, посмотрев, существуют ли они в HashMap. Это O (n).

Answer 3

как насчет этого:

1. объединить два массива
2. быстрая сортировка результата
3. шаг от массива [1] к массиву [array.length - 1] и проверьте массив [i] по отношению к массиву [i-1]

, если они совпадают, у вас есть дубликат.Это также должно быть O (n * log (n)) и не требовать двоичного поиска для каждой проверки.

Answer 4

Эта проблема также поддается распараллеливанию: порождает n1 потоки и каждый из них сравнивает элемент a1 с n2 элементами a2, а затем суммирует значения.Возможно, медленнее, но интересно рассмотреть, порождает n1 * n2 потоков для одновременного выполнения всех сравнений, а затем сокращается.Если P >> max (n1, n2) в первом случае, P >> n1 * n2 во втором, вы можете сделать все это за O (n) в первом случае, O (log n) во втором.

Answer 5

Я не знаю, самый ли это быстрый способ, но вы можете сделать

int[] a1 = new []{1,2,4,5,0};
int[] a2 = new []{2,4,11,-6,7};
var result = a1.Intersect(a2).Count();

Стоит сравнить это с другими способами, оптимизированными для int, поскольку Intersect () работает с IEnumerable.

Answer 6

У меня есть два метода, которые мне известны (ref: http://www2.cs.siu.edu/~mengxia/Courses%20PPT/220/carrano_ppt08.ppt):

Рекурсивный (псевдокод)

Algorithm to search a[first] through a[last] for desiredItem
if (there are no elements to search)
    return false
else if (desiredItem equals a[first])
    return true
else    
    return the result of searching a[first+1] through a[last]

Эффективность

May be O(log n) though I have not tried it.

последовательный поиск (псевдокод)

public boolean contains(Object anEntry)
{   
    boolean found = false;
    for (int index = 0; !found && (index < length); index++) {
    if (anEntry.equals(entry[index]))
            found = true;
    } 
    return found;
} 

эффективность последовательного поиска

Best case  O(1)
    Locate desired item first
Worst case  O(n)
    Must look at all the items
Average case O(n)
    Must look at half the items 
    O(n/2) is still O(n)

Iмне неизвестен алгоритм поиска O (log n), если он не отсортирован.

Answer 7

Вы можете использовать LINQ:

var a1 = new int[5] {1, 2, 4, 5, 0};
var a2 = new int[5] {2, 4, 11, -6, 7};
var matches = a1.Intersect(a2).Count();

Я не уверен, просто ли вы просите прямой или самый быстрый / лучший способ из возможных ...