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