Бинарный поиск через 2 массива - PullRequest
Новая
       8

Бинарный поиск через 2 массива

0 голосов
/ 27 апреля 2018

Я ищу дубликаты между двумя массивами. 

int[] f = {17,17,22,19};
int[] m = {21,19,24,22,20,23,18};
for(int i = 0; i < m.length; i++)
    {
         for(int j = 0; j < f.length; j++)
        {
             if(m[i] == f[j])
            {
                System.out.printf(m[i] + " ");//showing common 
            }
        }
    }

в настоящее время мой код ищет его в n ^ 2, однако я пытаюсь улучшить свои коды, чтобы они выполнялись со сложностью времени O (LogN) вместо O (N ^ 2). Есть ли способ, которым я могу реализовать алгоритм двоичного поиска для поиска между 2 массивами?

Ответы [ 4 ]

0 голосов
/ 27 апреля 2018

Во-первых, бинарный поиск для отсортированных массивов. Во-вторых, даже если вы сортируете массивы, сортировка массивов имеет сложность O (nlog n), которая больше, чем ниже, приближается к O (n).

Поскольку вам нужно найти дубликаты, Hashmap пригодится. Hashmap put () имеет сложность O (1) и возвращает старое значение, связанное с ключом.

Приведенный ниже код имеет сложность O (n), где n - длина самого длинного массива. Но это происходит за счет дополнительного места на карте. 

    int[] f = {17, 17, 22, 19};
    int[] m = {21, 19, 24, 22, 20, 23, 18};
    Map<Integer, Integer> unique = new HashMap<>();

    for(int j = 0; j < f.length; j++) {
         unique.put(f[j], 1);
     }

    for(int i = 0; i < m.length; i++) {
        Integer temp = unique.put(m[i], 2);
        if(temp != null && temp == 1) {

             System.out.printf(m[i] + " ");
         }
    }
0 голосов
/ 27 апреля 2018

Вы можете достичь N log N . 

Arrays.sort(f); // Cost N log N.
Arrays.sort(m);
int fi = 0;
int mi = 0;
while (fi < f.length && mi < f.length) { // Cost N
    int c = Integer.compare(f[fi], m[mi]);
    if (c == 0) {
        System.out.printf("Duplicate %d.%n", f[fi]);
        ++fi;
        ++mi
    } else if (c < 0) {
        ++fi;
        // Speed improvement, unneeded heuristic:
        int ix = Array.binarySearch(f, fi, f.length);
        if (ix < 0) {
            fi = ~ix + 1; // Not found => insert position + 1.
        } else {
            fi = ix; // Found.
        }
    } else {
        ++mi;
        // Speed improvement, unneeded heuristic:
        int ix = Array.binarySearch(m, mi, f.length);
        if (ix < 0) {
            mi = ~ix + 1; // Not found => insert position + 1.
        } else {
            mi = ix; // Found.
        }
    }
}
0 голосов
/ 27 апреля 2018

Вы можете создать набор, используя элементы первого массива, а затем проверить, присутствуют ли какие-либо элементы во втором массиве в наборе.

Если диапазон возможных значений ограничен, таблица прямого адреса (простой массив с одним индексом для каждого возможного значения) будет O (n).

В качестве альтернативы, используя Java 8 HashSet (который ухудшается до дерева при столкновениях), операции обычно O (1) амортизируются и O (log n) в худшем случае. Так что в худшем случае это будет O (n) или O (n log n).

0 голосов
/ 27 апреля 2018

Для заданных двух массивов длины f и m я думаю, что наилучшим подходом может быть сортировка большего массива, скажем m[], с использованием сортировки слиянием, которая даст сложность O(m*log(m)), и использование двоичного поиска для отсортированных m[] для каждого элемента f[], что даст сложность O(f*log(m)). В худшем случае сложность составит около O(log(m)*(m+f)). Если f<<m нам повезет !!

...