Поиск k-ой порядковой статистики в двух массивах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Совсем не наивное решение)
(Совсем не наивное решение)
Строка 21: Строка 21:
 
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.  
 
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.  
  
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j</tex> {{---}} <tex>1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j</tex> {{---}} <tex>2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j</tex> {{---}} <tex>2]</tex>), а значит элемент с номером <tex>i</tex> и все до него в массиве <tex>A</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой. Аналогично элемент с индексом <tex>j</tex> и все элементы, стоящие после него, в массиве <tex>B</tex> никогда не будут ответом, так как на позиции <tex>j</tex> будет стоять <tex>(i + j + 2)</tex>-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве <tex>A</tex> только в диапазоне индексов <tex>[i + 1, n</tex> {{---}} <tex>1]</tex>, а в массиве <tex>B</tex> {{---}} <tex>[0, j</tex> {{---}} <tex>1]</tex>. Также, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i</tex> {{---}} <tex>1]</tex>. Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i</tex> {{---}} <tex>1]</tex>, в массиве <tex>B</tex> {{---}} <tex>[j + 1, m</tex> {{---}} <tex>1]</tex>.
+
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j</tex> {{---}} <tex>1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j</tex> {{---}} <tex>2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j</tex> {{---}} <tex>2]</tex>), а значит элемент с номером <tex>i</tex> и все до него в массиве <tex>A</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой. Аналогично элемент с индексом <tex>j</tex> и все элементы, стоящие после него, в массиве <tex>B</tex> никогда не будут ответом, так как на позиции <tex>j</tex> будет стоять <tex>(i + j + 2)</tex>-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве <tex>A</tex> только в диапазоне индексов <tex>[i + 1, n</tex> {{---}} <tex>1]</tex>, а в массиве <tex>B</tex> {{---}} <tex>[0, j</tex> {{---}} <tex>1]</tex>. Также, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i</tex> {{---}} <tex>1]</tex>. Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i</tex> {{---}} <tex>1]</tex>, в массиве <tex>B</tex> {{---}} <tex>[j + 1, m</tex> {{---}} <tex>1]</tex>.  
  
  <font color=green>// во избежание коллизий перед вызовом функции проинициализируем A[n] = +INF, B[m] = +INF </font>
+
Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <tex>k</tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>findKthOrderStatistic(A, min(n, k - 1), B, min(m, k - 1), k)</tex>.
 +
 
 +
<font color=green>// во избежание коллизий перед вызовом функции проинициализируем A[n] = +INF, B[m] = +INF  
 +
//  
 
  '''int''' findKthOrderStatistic('''int[]''' A, '''int''' n, '''int[]''' B, '''int''' m, '''int''' k):  
 
  '''int''' findKthOrderStatistic('''int[]''' A, '''int''' n, '''int[]''' B, '''int''' m, '''int''' k):  
 
   '''int''' i = n * (k - 1) / (n + m)
 
   '''int''' i = n * (k - 1) / (n + m)

Версия 22:25, 17 апреля 2015

Задача:
Пусть даны два отсортированных массива [math]A[/math] и [math]B[/math] размерами [math]n[/math] и [math]m[/math] соответственно. Требуется найти [math]k[/math]-ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля.


Варианты решения

Наивное решение

Сольем два массива и просто возьмем элемент с индексом [math]k[/math][math]1[/math]. Сливание будет выполнено за [math]O(n + m)[/math] c использованием дополнительной памяти, что является существенным недостатком.

Чуть менее наивное решение

Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После [math](k[/math][math]1)[/math]-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим [math]k[/math]-ый элемент за [math]O(k)[/math] шагов.

Совсем не наивное решение

Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях [math]k[/math]. Следующее решение работает за [math]O(log(n) + log(m))[/math].

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

Рассмотрим следующую ситуацию: пусть у нас есть элемент [math]a[i][/math] из массива [math]A[/math] и элемент [math]b[j][/math] из массива [math]B[/math] и они связаны неравенством [math]b[j[/math][math]1] \lt a[i] \lt b[j][/math]. Тогда [math]a[i][/math] есть [math](j + i + 1)[/math]-ый порядковый элемент после слияния массивов. Это объясняется тем, что до [math]a[i][/math]-ого элемента идут [math](j[/math][math]1)[/math] элемент из массива [math]B[/math], [math]i[/math] элементов из массива [math]A[/math] (включая сам элемент [math]a[i][/math]). В итоге получаем [math](j[/math][math]1) + i + 2 = j + i + 1[/math]. Принимая это во внимание, будем выбирать [math]i[/math] и [math]j[/math] таким образом, чтобы [math]j + i + 1 = k[/math].

Подведем промежуточный итог:

  1. Инвариант [math]j + i = k[/math][math]1[/math]
  2. Если [math]b[j[/math][math]1] \lt a[i] \lt b[j][/math], то [math]a[i][/math] и есть [math]k[/math]-ая порядковая статистика
  3. Если [math]a[i[/math][math]1] \lt b[j] \lt a[i][/math], то [math]b[j][/math] и есть [math]k[/math]-ая порядковая статистика

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

Будем использовать [math]i[/math] и [math]j[/math] как опорные точки для разделения массивов. Заметим, что если [math]a[i] \lt b[j][/math], то [math]a[i] \lt b[j[/math][math]1][/math] (иначе второе условие бы выполнялось). В таком случае на месте [math]i[/math]-го элемента может стоять максимум [math]i + (j[/math][math]2) + 2 = (i + j)[/math]-ый порядковый элемент после слияния массивов (так произойдет в случае, когда [math]a[i] \gt b[j[/math][math]2][/math]), а значит элемент с номером [math]i[/math] и все до него в массиве [math]A[/math] никогда не будут [math]k[/math]-ой порядковой статистикой. Аналогично элемент с индексом [math]j[/math] и все элементы, стоящие после него, в массиве [math]B[/math] никогда не будут ответом, так как на позиции [math]j[/math] будет стоять [math](i + j + 2)[/math]-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве [math]A[/math] только в диапазоне индексов [math][i + 1, n[/math][math]1][/math], а в массиве [math]B[/math][math][0, j[/math][math]1][/math]. Также, если [math]b[j] \lt a[i][/math], то [math]b[j] \lt a[i[/math][math]1][/math]. Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве [math]A[/math] в диапазоне [math][0, i[/math][math]1][/math], в массиве [math]B[/math][math][j + 1, m[/math][math]1][/math].

Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от [math]k[/math]-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров [math]findKthOrderStatistic(A, min(n, k - 1), B, min(m, k - 1), k)[/math].

// во избежание коллизий перед вызовом функции проинициализируем A[n] = +INF, B[m] = +INF 
// 
int findKthOrderStatistic(int[] A, int n, int[] B, int m, int k): 
  int i = n * (k - 1) / (n + m)
  int j = (k - 1) - i
  // чтобы сохранить инвариант, сделаем A[-1] = -INF и B[-1] = -INF 
  int Ai_left = ((i == 0) ? INT_MIN : A[i-1])
  int Bj_left = ((j == 0) ? INT_MIN : B[j-1])
  if (Bj_left < Ai and Ai < Bj):
    return Ai
  else if (Ai_left < Bj and Bj < Ai):
    return Bj
  if (Ai < Bj):
    return findKthOrderStatistic(A + i + 1, n - i - 1, B, j, k - i - 1)
  else
    return findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)

См. также

Источники информации