Сравнение между двумя массивами

Question

Как сравнить два массива с отсортированным содержимым целого в двоичном алгоритме?

Answer 1

Как в каждом случае: это зависит.

Если предположить, что массивы упорядочены или хэшированы, сложность времени не превышает O (n + m).

Вы не упомянули ни один язык, так что это псевдокод.

function SortedSequenceOverlap(Enumerator1, Enumerator2)
{ while (Enumerator1 is not at the end and Enumerator2 is not at the end)
  { if (Enumerator1.current > Enumerator2.current)
      Enumerator2.fetchNext()
    else if (Enumerator2.current > Enumerator1.current)
      Enumerator1.fetchNext()
    else
      return true
  }
  return false
}

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

---

Однако, это не всегда самый быстрый способ.

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

Этоможет быть еще более улучшено, потому что, когда вы начинаете с медианного элемента небольшого массива, вам не нужно выполнять полный поиск для любого дополнительного элемента.Любой элемент до медианного элемента должен находиться в диапазоне до местоположения, в котором медианный элемент не был найден, а любой элемент после медианного элемента должен находиться вверхний диапазон большого массива.Это может быть применено рекурсивно, пока все элементы не будут найдены.Получив удар, вы можете прервать его.

Недостаток этого метода в том, что в худшем случае он занимает больше времени, т. Е. O (n log m), и требует произвольного доступа к массивам, которые могут повлиятьэффективность кэша.

С другой стороны, умножение на маленькое число (log m) может быть лучше, чем добавление большого числа (m).В отличие от вышеупомянутого алгоритма, обычно требуется доступ только к нескольким элементам большого массива.

Разрыв примерно равен, когда log m меньше m / n, где n - меньшее число.

---

Вы думаете, это все?- нет

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

Почему это должно быть быстрее? У вас естьчтобы найти гораздо больше элементов.

Ответ:

• Нет, больше нет поисков.Как только границы, где вы ожидаете, что диапазон элементов большого массива разрушится, вы можете прекратить поиск этих элементов, так как вы больше не найдете попаданий.На самом деле количество сравнений точно такое же.

• Разница в том, что один элемент большого массива сравнивается с различными элементами малого массива впервый шаг.Это займет всего лишь один медленный доступ для множества сравнений, в то время как наоборот вам нужно получить доступ к одному и тому же элементу несколько раз с некоторыми другими элементами.Таким образом, есть менее медленных доступа за счет более быстрых.

(Я реализовал поиск, когда вы печатаете таким образом, около 30 лет назад, когда доступ к большомуиндекс требуемого дискового ввода-вывода.)

Answer 2

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

Answer 3

Это можно сделать двумя способами.a) Бинарный поиск b) Линейный поиск

Для бинарного поиска - для каждого элемента в массиве Ищите элемент в B с помощью бинарного поиска, тогда в этом случае сложность O (n log n)

Для линейного поиска - это O (m + n) - где m, n - размеры массивов.В вашем случае m = n.

Линейный поиск:

1. Имеют два индекса i, j, которые указывают на массивы A, B
2. Сравнить A [i], B [j]
3. Если A [i] Если A [i]> B [j], тоувеличение j, потому что любое совпадение, если оно существует, можно найти только в более поздних индексах в B.
4. Если A [i] == B [j], вы нашли ответ.

Код:

private int findCommonElement(int[] A, int[] B) {

    for ( int i = 0, j = 0; i < A.length && j < B.length;  ) {
      if ( A[i] < B[j] ) {
        i++;
      } else if ( A[i] > B[j] ) {
        j++;
      }
      return A[i];
    }
    return -1; //Assuming all integers are positive.
}

Теперь, если у вас есть оба по убыванию, просто поменяйте местами знаки сравнения, т. Е. Если A[i] < B[j] увеличение j еще увеличение i

Если у вас есть одно снижение (B)один восходящий (A), затем i для A начинается с начала массива и j для B начинается с конца массива и соответственно перемещает их, как показано ниже:

for (int i = 0, j = B.length - 1; i < A.length && j >= 0; ) {
   if ( A[i] < B[j] ) {
       i++;
   } else if ( A[i] > B[j] ) {
       j--;
   }
   return A[i];
}

Answer 4

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

Все еще лучше, чем грубая сила O (n2).