Поиск целых чисел в массиве, образованных объединением двух отсортированных массивов

Question

Мне задали этот вопрос в интервью. Есть два отсортированных массива размера N и M, и они объединены вместе, так что результирующий массив не сортируется. В результате элементы массива от 0 до N-1 относятся к первому массиву, а элементы из N в M + N-1 - из вторых массивов.

Как найти целое число в таких массивах. Оба массива содержат уникальные элементы, и между двумя исходными массивами нет пересечения. Сложность времени должна быть O (log (N + M)), а сложность пространства должна быть O (1).

например.

Массив 1 [3,4,5] Массив 2 [1,2] полученный массив [3,4,5,1,2]

Как искать в этом массиве?

Answer 1

Давайте используем подход слияния.

Теперь перейти к последнему шагу, здесь мы имеем 2 массивов, которые сортируют и которые должны быть объединены в единый список.

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

Таким же образом мы ищем элемент, рассматривающий эти два массива.

Answer 2

Так как сортируются массивы [0,N-1] и [N,N+M-1]. вы можете использовать binary search в обоих массивах, что приведет к сложности log(N)+log(M) с пространственной сложностью O(1).

Answer 3

Если вы знаете N и M, тогда это легко. Сначала выполните двоичный поиск в первой части, затем во второй части. Сложность времени - O(log(N)) + (O(log(M)) <= O(log(N+M)).

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

Answer 4

O (журнал (М) + журнал (N)) больше, чем O (журнал (М + Н)), но не более чем в два раза:

O (журнал (М + Н)) < = O (log (M) + log (N)) < = 2 * O (log (M + N))

Answer 5

Я мог бы подумать об этом оптимальном решении, и я предполагаю, что сложность времени - O (Nlog (MN)), учитывая N < M.

1. Идите по объединенному массиву в обоих направлениях одновременно. Предполагая, что оба предыдущих массива отсортированы в порядке возрастания, один итератор начнется с 0 и повторит в прямом направлении в поисках точки , где массивы соединены. Другой итератор будет перебираться с конца и двигаться назад, ища точку соединения.
2. В каждой итерации мы сравниваем значение прямого и обратного
   итератора для поиска целого K.

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

   class cls 
   { 
       public int search(int merged[], int x) 
       { 
        int ret = -1, a = 0 , b = 0; 
        boolean arrn = false; 
        //a is forward and b is backward iterator 
        //looking for index where arrays are joined. 
        for(b = merged.length - 1;a < b ;a++,b--) 
        { 
         //compare values of iterator to K 
         if(merged[a] == x) 
         { 
          ret = a; 
          return ret; 
         } 
   
         if (merged[b] == x) 
         { 
          ret = b; 
          return ret; 
         } 
   
         //if a is the point where first array ends then 
         //do binarysearch in remaining element of array which 
         //are not visited by both a and b. Since original arrays 
         // soreted. It is guaranteed that a+1 to b is also sorted. 
         // 
         if (!(merged[a] < merged[a + 1])) 
         { 
          ret = Arrays.binarySearch(merged, a+1, b, x); 
          return ret; 
         } 
   
         if (!(merged[b - 1] < merged[b])) 
         { 
          ret = Arrays.binarySearch(merged, a + 1, b - 1, x); 
          return ret; 
         } 
        } 
        return ret; 
       } 
   

   }