алгоритм для сравнения отсортированного массива

Question

У меня есть два отсортированных массива. Мне нужно найти, если оба они разные.

Эти массивы имеют элементы в диапазоне определенного диапазона.

Более того, один элемент может быть другим.

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

грубый пример:

Вход:

array1: 1 2 4 5 8 9 12 
array2: 1 4 8 10 12 13 14 

Здесь диапазон 1-15.

Каков наиболее оптимальный алгоритм сравнения?

Я также могу указать различия и сходства, например. 4 находится в обоих и 5 отсутствует во втором массиве.

Мое решение:

1. Два указателя для отслеживания индекса массива.

2. Направьте их в начало массива.

3. Начать сравнение первых двух элементов.

4. Если оба равны -> перейдите к следующему.
   еще

   1. Найти наибольший из двух элементов массива. Например, массив1 имеет больший элемент.

   2. Двоичный поиск элемента в другом массиве (array2) -.> Поз этого элемента в этом массиве сказать позы

   3. Отклона элементы массива до пос.

5. Указатели приращения. отменить это часть массива до этого указатели. повторение.

Это имеет сложность n log n (намного меньше, чем в среднем, это когда вы должны сделать поиск для каждого элемента).

Answer 1

(4.) - вместо двоичного поиска выполните линейный поиск.

Общая сложность: O (n) - при посещении каждого пункта ровно один раз.

Answer 2

Поскольку оба массива отсортированы. Лучше всего использовать линейный поиск.

Answer 3

Если массивы были блоками памяти - то, что вы могли бы выделить с помощью malloc, вы можете ускорить сравнение, отбросив массив до 32 или 64-битных целых чисел. Таким образом, вы сможете сравнить несколько элементов массива с одним тестом ==.

Также, если вы хотите, чтобы массив имел определенное количество элементов, тогда разворачивайте цикл, скажем, 8, если операторы будут быстрее. Он сохранит сравнение и прыжок в конце каждого прогона через цикл.

Answer 4

Полностью непроверенные (и не работает хорошо, когда есть дубликаты):

var same = new List<int>(); 
var inAonly = new List<int>(); 
var inBonly = new List<int>(); 

int b = 0; 
int a = 0; 
//first look at all the elements until one of the lists run out of elements 
for(; a < inputa.Count && b < inputb.Count;) { 
    //if element is the same, then add to same 
    //and the problem with duplicates is found here, if a contains two "1", but b only contains one, then same will report a single "1", but inAonly will also contain a "1" 
    if (inputa[a] == inputb[b]){ 
     same.Add(inputa[a]); 
     a++; 
     b++; 
    } 
    //otherwise, we check if a < b, if that is the case, we know that a only exists in a, otherwise it must only exist in b. 
    else if (inputa[a] < inputb[b]) 
    { 
     inAonly.Add(inputa[a]); 
     a++ 
    } else   { 
     inBonly.Add(inputb[b]); 
     b++ 
    } 
} 
//add the rest of the elements if one array is longer than the other 
for(; a < inputa.Count;a++) 
    inAonly.Add(inputa[a]); 
for(; b < inputb.Count;b++) 
    inBonly.Add(inputb[b]); 

Answer 5

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

Я думаю, что сложность будет лучше, чем nlgn, так как вам не нужно искать в полном массиве при каждой разнице. Это потому, что вы отбрасываете элементы до pos.

Answer 6

Если array1 и array2 имеют одинаковый размер, то перебирайте их и сравнивайте их по элементам. Когда найдено первое различие =>, массивы разные. Если вы достигнете конца массивов, значит, они равны. Сложность - O (длина массива) во времени и O (1) в памяти.

Если array1 и array2 имеют разный размер, выделите другой массив с размером - диапазон элементов и инициализируйте его нулями (array3). Для каждого элемента в Array1 приращения элемента в array3, как это: array3 [Array1 [я]] ++

После этого итерации точно так же array2, но декремент: array3 [array2 [я]] -

После что для каждого элемента в array3 у вас есть 3 возможности:

• если array3 [я] == 1 // то элемент я в array1, но не в массив2
• если array3 [я] == -1// then элемент i находится в array2, но не в array1
• if array3 [i] == 0 // тогда элемент i находится в b других массивов или ни в одном из них.

Сложность по времени - O (диапазон), сложность памяти - O (диапазон). Если диапазон не начинается с 0, вы можете сделать смещение для каждого индекса.

Пример:

• диапазон: 1-15
• массив1: 1 2 4 5 8 9 12
• массив2: 1 4 8 10 12 13 14

После step1 array3 будет выглядеть так:

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

value: 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 

После шага 2 массив3 будет выглядеть l ike:

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

value: 0 1 0 0 1 0 0 0 1 -1 0 0 -1 -1 0 

Answer 7

Вы на правильном пути, насколько хотите, но поиск не требуется.(См дно для фактического алгоритма)

начать с 2 указателей, указывающих на начало:

 v 
array1: 1 2 4 5 8 9 12 

     v 
array2: 1 4 8 10 12 13 14 

(так же, как у вас есть), если элементы такие же добавить их к вам "In-Both" установлен, то приращение как указатели, так что теперь мы имеем:

  v 
array1: 1 2 4 5 8 9 12 

      v 
array2: 1 4 8 10 12 13 14 

Итак, теперь мы сталкиваемся с различными элементами, вместо того, чтобы искать здесь мы можем воспользоваться тем, что мы знаем, за то, что не может быть 2 в прошлом, где POIN ter находится в array2, поэтому мы добавляем 2 в наш комплект "Only_in_array1". и приращение только array1 указатель. так что мы в конечном итоге с:

  v 
array1: 1 2 4 5 8 9 12 

      v 
array2: 1 4 8 10 12 13 14 

Мы в конечном итоге с совпадающими поэтому мы добавляем 4 к "In-Both" и увеличиваем оба указателя:

   v 
array1: 1 2 4 5 8 9 12 

      v 
array2: 1 4 8 10 12 13 14 

Если продолжить эту модель вы в конечном итоге в конечном итоге с:

     v 
array1: 1 2 4 5 8 9 12 

        v 
array2: 1 4 8 10 12 13 14 

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

Обобщить алгоритм:

• Старт с 2 указателями на старте обоих массивов (и инициализации и datastructures вы хотите хранить информацию: Я использовал 3 списки/наборы)

• Теперь вы можете иметь один из трех случаев

  1. значение p1 равно p2: Добавить значение для вашего in both массива и увеличивают как

  2. значение p1 меньше p2: Добавить значение p1 ваших only in array1 массива и увеличивают только p1

  3. значение p1 больше p2: Добавить значение p2 ваших only in array2 массива и приращения только p2

• Петлю на тех условиях, пока не будет достигнут конец одного (или обоих, если это происходит именно так) ваших массивов. Затем добавьте все остальные предметы в другой список в его список only in arrayX.

Этот алгоритм только поражает каждый предмет один раз, так что должно быть O (п). Надеюсь, это поможет