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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Совсем не наивное решение)
м (Совсем не наивное решение)
(не показано 26 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = Пусть даны два отсортированных массива <tex>A</tex> и <tex>B</tex> размерами <tex>n</tex> и <tex>m</tex> соответственно. Требуется [[Поиск k-ой порядковой статистики|найти <tex>k</tex>-ый порядковый элемент]] после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля.}}
+
|definition = Даны два отсортированных массива <tex>a</tex> и <tex>b</tex> размерами <tex>n</tex> и <tex>m</tex> соответственно. Требуется [[Поиск k-ой порядковой статистики|найти <tex>k</tex>-ый порядковый элемент]] после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля.}}
  
 
== Варианты решения ==
 
== Варианты решения ==
 
=== Наивное решение ===
 
=== Наивное решение ===
Сольем два массива и просто возьмем элемент с индексом <tex>k - 1</tex>. Сливание будет выполнено за <tex>O(n + m)</tex> c использованием дополнительной памяти, что является существенным недостатком.
+
Сольем два массива и просто возьмем элемент с индексом <tex>k - 1</tex>. Слияние будет выполнено за время <tex>O(n + m)</tex>, к тому же этот алгоритм использует <tex>O(n + m)</tex> дополнительной памяти.
 +
 
 
=== Чуть менее наивное решение ===
 
=== Чуть менее наивное решение ===
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k - 1)</tex>-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
+
Будем использовать два указателя, с помощью которых сможем обойти массивы, не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k - 1)</tex>-ой итерации сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
 +
 
 
=== Еще одно решение ===
 
=== Еще одно решение ===
В первом массиве выберем серединный элемент <tex>(i = n / 2)</tex> и бинпоиском найдем во втором массиве позицию <tex>j</tex>, на котором стоит наибольший элемент, меньший <tex>a[i]</tex>. Если <tex>i + j = k - 2</tex>, то мы нашли <tex>k</tex>-ую порядковую статистику {{---}} это элемент <tex>a[i]</tex>. Иначе, если <tex>i + j > k - 2</tex>, то далее тем же способом ищем в массиве <tex>A</tex> в диапазоне индексов <tex>[0, i - 1]</tex>, а если <tex>i + j < k - 2</tex>, то в диапазоне индексов <tex>[i + 1, n - 1]</tex>. Решая задачу таким способом, мы получим асимптотику <tex>O(\log(n) \cdot \log(m))</tex>.
+
В первом массиве выберем элемент c индексом <tex>i = \dfrac{n}{2}</tex> и [[Целочисленный двоичный поиск|бинарным поиском]] найдем во втором массиве позицию <tex>j</tex>, на которой стоит наибольший элемент, меньший <tex>a[i]</tex>. Если <tex>i + j = k - 2</tex>, то мы нашли <tex>k</tex>-ую порядковую статистику {{---}} это элемент <tex>a[i]</tex>. Иначе, если <tex>i + j > k - 2</tex>, то далее тем же способом ищем в массиве <tex>a</tex> в диапазоне индексов <tex>[0, i - 1]</tex>, а если <tex>i + j < k - 2</tex>, то в диапазоне индексов <tex>[i + 1, n - 1]</tex>. Решая задачу таким способом, мы получим асимптотику <tex>O(\log(n) \cdot \log(m))</tex>.
 +
 
 
=== Совсем не наивное решение ===
 
=== Совсем не наивное решение ===
Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях <tex>k</tex>. Следующее решение работает за <tex>O(\log(n) + \log(m))</tex>.
+
Приведём теперь решение, работающее за время <tex>O(\log(\min(n, m)))</tex>.
  
Чтобы получить логарифмическую сложность, будем использовать [[Целочисленный двоичный поиск|бинарный поиск]], который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов.
+
Для начала рассмотрим следующую ситуацию: пусть у нас есть элемент <tex>a[i]</tex> из массива <tex>a</tex> и элемент <tex>b[j]</tex> из массива <tex>b</tex> и они связаны неравенством <tex>b[j - 1] < a[i] < b[j]</tex>. Тогда <tex>a[i]</tex> есть <tex>(j + i + 1)</tex>-ый порядковый элемент после слияния массивов. Это объясняется тем, что до <tex>a[i]</tex>-ого элемента идут <tex>j</tex> элементов из массива <tex>b</tex>, <tex>(i+1)</tex> элементов из массива <tex>a</tex> (включая сам элемент <tex>a[i]</tex>). В итоге получаем <tex>j + i + 1</tex>. Принимая это во внимание, будем выбирать <tex>i</tex> и <tex>j</tex> таким образом, чтобы <tex>j + i + 1 = k</tex>.
 
 
Рассмотрим следующую ситуацию: пусть у нас есть элемент <tex>a[i]</tex> из массива <tex>A</tex> и элемент <tex>b[j]</tex> из массива <tex>B</tex> и они связаны неравенством <tex>b[j - 1] < a[i] < b[j]</tex>. Тогда <tex>a[i]</tex> есть <tex>(j + i + 1)</tex>-ый порядковый элемент после слияния массивов. Это объясняется тем, что до <tex>a[i]</tex>-ого элемента идут <tex>(j - 1)</tex> элемент из массива <tex>B</tex>, <tex>i</tex> элементов из массива <tex>A</tex> (включая сам элемент <tex>a[i]</tex>). В итоге получаем <tex>j + i + 1</tex>. Принимая это во внимание, будем выбирать <tex>i</tex> и <tex>j</tex> таким образом, чтобы <tex>j + i + 1 = k</tex>.
 
 
   
 
   
 
Подведем промежуточный итог:
 
Подведем промежуточный итог:
Строка 23: Строка 24:
 
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.  
 
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.  
  
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j - 1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j - 2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j - 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 - 1]</tex>, а в массиве <tex>B</tex> {{---}} <tex>[0, j - 1]</tex>. По аналогии, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i - 1]</tex> (иначе выполнялось бы третье условие). Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i - 1]</tex>, в массиве <tex>B</tex> {{---}} <tex>[j + 1, m - 1]</tex>.
+
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j - 1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j - 2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j - 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 - 1]</tex>, а в массиве <tex>b</tex> {{---}} <tex>[0, j - 1]</tex>. По аналогии, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i - 1]</tex> (иначе выполнялось бы третье условие). Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>a</tex> в диапазоне <tex>[0, i - 1]</tex>, в массиве <tex>b</tex> {{---}} <tex>[j + 1, m - 1]</tex>.  
 
 
Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <tex>k</tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>findKthOrderStatistic(A, \min(n, k - 1), B, \min(m, k - 1), k)</tex>.
 
  
  <tex>\mathtt{findKthOrderStatistic}</tex>('''int*''' A, '''int''' n, '''int*''' B, '''int''' m, '''int''' k):  
+
Стоит отметить, что нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <tex>k</tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>\mathtt{findKthOrderStatistic}(a, \min(n, k), b, \min(m, k), k)</tex>.
   '''if''' (n == 1):
+
 
    '''int''' tmp = binSearch(B, m, A[0]) <font color=green>// вернет позицию, на которой должен стоять элемент A[0] в массиве B </font>
+
'''int''' findKthOrderStatistic('''int*''' a, '''int''' n, '''int*''' b, '''int''' m, '''int''' k):  
     '''if''' (tmp > k):
+
   '''if''' n == 1 <font color=green>// в этом случае можно сразу дать ответ </font>
       '''return''' B[k - 1]
+
     '''if''' b[k - 1] < a[0]
     '''else if''' (tmp == k):
+
       '''return''' b[k - 1]
       '''return''' A[0]
+
     '''else if ''' a[0] < b[k - 2]
 +
       '''return''' b[k - 2]
 
     '''else'''
 
     '''else'''
       '''return''' B[k - 2]
+
       '''return''' a[0]
 +
  '''if''' m == 1 <font color=green>// симметричен случаю с n = 1 </font>
 +
      '''return''' findKthOrderStatistic(b, m, a, n, k)
 
   '''int''' i = n / 2
 
   '''int''' i = n / 2
 
   '''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
 
   '''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
   '''if''' (j >= m):
+
   '''if''' j >= m
     '''return''' findKthOrderStatistic(A + i + 1, n - i - 1, B, m, k)
+
     '''return''' findKthOrderStatistic(a + i + 1, n - i - 1, b, m, k - i - 1)
   <font color=green>// чтобы сохранить инвариант, сделаем A[-1] = -INF и B[-1] = -INF </font>
+
   <font color=green>// чтобы сохранить инвариант, сделаем a[-1] = -INF и b[-1] = -INF </font>
   '''int''' Ai_left = ((i == 0) ? INT_MIN : A[i-1])
+
   '''int''' aiLeft = ((i == 0) ? INT_MIN : a[i - 1])
   '''int''' Bj_left = ((j == 0) ? INT_MIN : B[j-1])
+
   '''int''' bjLeft = ((j == 0) ? INT_MIN : b[j - 1])
   '''if''' (Bj_left < Ai and Ai < Bj):
+
   '''if''' bjLeft < a[i] '''and''' a[i] < b[j]
     '''return''' Ai
+
     '''return''' a[i]
   '''else if''' (Ai_left < Bj and Bj < Ai):
+
   '''else if''' aiLeft < b[j] '''and''' b[j] < a[i]
     '''return''' Bj
+
     '''return''' b[j]
   '''if''' (Ai < Bj):
+
   '''if''' a[i] < b[j]
     '''return''' findKthOrderStatistic(A + i + 1, n - i - 1, B, j, k - i - 1)
+
     '''return''' findKthOrderStatistic(a + i + 1, n - i - 1, b, j, k - i - 1)
 
   '''else'''
 
   '''else'''
     '''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
+
     '''return''' findKthOrderStatistic(a, i, b + j + 1, m - j - 1, k - j - 1)
  
Таким образом первый массив на каждой итерации уменьшается в два раза, как только он становится маленьким (это произойдет за <tex>O(\log(n))</tex> операций), мы запустим бинпоиск и найдем ответ за <tex>O(\log(m))</tex>. Итоговая асимптотика {{---}} <tex>O(\log(n) + \log(m))</tex>.
+
Чтобы алгоритм работал за <tex>O(\log(\min(n, m)))</tex>, будем передавать первым массивом в функцию тот, длина которого меньше. Тогда  длина рассматриваемой области первого массива на каждой итерации уменьшается в два раза. После того, как она станет равна единице, ответ можно будет получить за несколько сравнений.
  
 
==См. также==
 
==См. также==

Версия 11:28, 19 апреля 2015

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


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

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

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

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

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

Еще одно решение

В первом массиве выберем элемент c индексом [math]i = \dfrac{n}{2}[/math] и бинарным поиском найдем во втором массиве позицию [math]j[/math], на которой стоит наибольший элемент, меньший [math]a[i][/math]. Если [math]i + j = k - 2[/math], то мы нашли [math]k[/math]-ую порядковую статистику — это элемент [math]a[i][/math]. Иначе, если [math]i + j \gt k - 2[/math], то далее тем же способом ищем в массиве [math]a[/math] в диапазоне индексов [math][0, i - 1][/math], а если [math]i + j \lt k - 2[/math], то в диапазоне индексов [math][i + 1, n - 1][/math]. Решая задачу таким способом, мы получим асимптотику [math]O(\log(n) \cdot \log(m))[/math].

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

Приведём теперь решение, работающее за время [math]O(\log(\min(n, m)))[/math].

Для начала рассмотрим следующую ситуацию: пусть у нас есть элемент [math]a[i][/math] из массива [math]a[/math] и элемент [math]b[j][/math] из массива [math]b[/math] и они связаны неравенством [math]b[j - 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]b[/math], [math](i+1)[/math] элементов из массива [math]a[/math] (включая сам элемент [math]a[i][/math]). В итоге получаем [math]j + i + 1[/math]. Принимая это во внимание, будем выбирать [math]i[/math] и [math]j[/math] таким образом, чтобы [math]j + i + 1 = k[/math].

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

  1. Инвариант [math]j + i = k - 1[/math]
  2. Если [math]b[j - 1] \lt a[i] \lt b[j][/math], то [math]a[i][/math] и есть [math]k[/math]-ая порядковая статистика
  3. Если [math]a[i - 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 - 1][/math] (иначе второе условие бы выполнялось). В таком случае на месте [math]i[/math]-го элемента может стоять максимум [math]i + (j - 2) + 2 = (i + j)[/math]-ый порядковый элемент после слияния массивов (так произойдет в случае, когда [math]a[i] \gt b[j - 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 - 1][/math], а в массиве [math]b[/math][math][0, j - 1][/math]. По аналогии, если [math]b[j] \lt a[i][/math], то [math]b[j] \lt a[i - 1][/math] (иначе выполнялось бы третье условие). Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве [math]a[/math] в диапазоне [math][0, i - 1][/math], в массиве [math]b[/math][math][j + 1, m - 1][/math].

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

int findKthOrderStatistic(int* a, int n, int* b, int m, int k): 
  if n == 1 // в этом случае можно сразу дать ответ 
    if b[k - 1] < a[0]
      return b[k - 1]
    else if  a[0] < b[k - 2]
      return b[k - 2]
    else
      return a[0]
  if m == 1 // симметричен случаю с n = 1 
      return findKthOrderStatistic(b, m, a, n, k)
  int i = n / 2
  int j = (k - 1) - i // j > 0, так как i <= (k / 2) 
  if j >= m
    return findKthOrderStatistic(a + i + 1, n - i - 1, b, m, k - i - 1)
  // чтобы сохранить инвариант, сделаем a[-1] = -INF и b[-1] = -INF 
  int aiLeft = ((i == 0) ? INT_MIN : a[i - 1])
  int bjLeft = ((j == 0) ? INT_MIN : b[j - 1])
  if bjLeft < a[i] and a[i] < b[j]
    return a[i]
  else if aiLeft < b[j] and b[j] < a[i]
    return b[j]
  if a[i] < b[j]
    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)

Чтобы алгоритм работал за [math]O(\log(\min(n, m)))[/math], будем передавать первым массивом в функцию тот, длина которого меньше. Тогда длина рассматриваемой области первого массива на каждой итерации уменьшается в два раза. После того, как она станет равна единице, ответ можно будет получить за несколько сравнений.

См. также

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