Эффективное определение количества меньших элементов для каждого элемента в массиве

Я застрял на этой проблеме:

Для заданного массива из первых натуральных чисел, произвольно переставленных, строится массив , так что - это число элементов от до которые меньше, чем , $A$ $n$ $B$ $B(k)$ $A(1)$ $A(k-1)$ $A(k)$

я) Учитывая вы можете найти в времени? II) Учитывая вы можете найти в времени? $A$ $B$ $O(n)$
$B$ $A$ $O(n)$

Здесь . Для конкретного примера: $B(1) = 0$

| \begin{matrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \end{matrix} |

$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$

Может кто-нибудь мне помочь? Спасибо.

algorithms arrays permutations проклятый
источник

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

O (n \log n)

$\mathcal O(n \log n)$

Реал Слав

@Merbs означает, что подсказка, которую вы дали, означает, что у вас есть решение?

AJed

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

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n\log n)$

O (n)

$O(n)$

Merbs

@Merbs. Я чувствую, что ваш намек может привести к правильному пути. У меня тоже есть одно решение (следуя вашей подсказке). Я предполагаю, что в анализе есть хитрость, которая заставляет его перейти к . Я думаю, что хитрость - это знание того, что идет только от 1: .

O (n)

$O(n)$

A

$A$

n

$n$

AJed

Эта статья также дает алгоритм . Вы уверены, что для этого существует алгоритм ?

O (n \log n)

$\mathcal O(n \log n)$

O (n)

$\mathcal O(n)$

Реал Слав

Ответы:

Наивный алгоритм определения из : $B$ $A$

Для , определите значение путем сравнения каждого с для и подсчета тех, которые удовлетворяют . $k=1,\dots,n$ $B(k)$ $A(i)$ $A(k)$ $i=1,\dots,k$ $A(i)<A(k)$

Этот алгоритм сравнивает со всеми остальными ( раз), с другими и т. Д., Поэтому общее количество сравнений равно . Но это не лучшее, что мы можем сделать. Например, глядя на , нам не нужно делать никаких сравнений! потому что это первые натуральных чисел, и гарантируется (независимо от перестановки), что там будут младших натуральных чисел. А как насчет ? Вместо проверки от до мы могли бы просто проверить . Это: $A(1)$ $n-1$ $A(2)$ $n-2$ $\frac{(n-1)(n-2)}{2}$ $B(n)$ $B(n)=A(n)-1$ $n$ $n-1$ $B(n-1)$ $A(1)$ $A(n-2)$ $A(n)$

Для , используйте алгоритм выше; для используйте обратный алгоритм: определите , предварительно установив для него значение а затем вычтя для каждой записи для меньше . $k=1, \dots,\frac{n}{2}$ $k=\frac{n}{2},\dots,n$ $B(k)$ $A(n)-1$ $1$ $A(i)$ $i=k+1,\dots,n$ $A(k)$

Это займет шагов, которые все еще . Отметим также, что при построении из , если то . $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ $O(n^2)$ $A$ $B$ $B(n)=A(n)-1$ $A(n)=B(n)+1$

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

| \begin{matrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 \end{matrix} |

$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$

Вместо того, чтобы проверять их все (или проверять их по порядку), мы могли бы использовать бинарный поиск для определения каждого . Однако сортировка по-прежнему занимает время . $B(k)$ $O(n\log n)$

Merbs
источник

Это была только моя первая идея; хотя я понимаю, что проблема более интересна, чем я изначально ее считал. И у меня еще не было возможности прочитать результаты Realz Slaw, поэтому алгоритм может быть отключен.

Мерб

Вместо того, чтобы определять каждый одному за раз, мы можем смотреть в будущее и проходить каждое число в только один раз ! Но мы будем использовать пробел: $B(k)$ $A$ $n$

| \begin{matrix} A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & B \\ 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 4 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 0 \\ 3 & 0 & 0 & 0 & 1 & 2 & 2 & 2 & 2 & 3 & 0 \\ 1 & 0 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & 0 \\ 7 & 0 & 1 & 1 & 2 & 3 & 3 & 3 & 4 & 5 & 3 \\ 2 & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & 6 & 1 \\ 9 & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & 6 & 6 \\ 6 & 0 & 1 & 2 & 3 & 4 & 4 & 5 & 6 & 7 & 4 \\ 5 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 4 \end{matrix} |

$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$

Мы могли бы сэкономить еще больше времени, не обновляя те, которые уже были определены (то есть, нет смысла обновлять после первого шага), но в худшем случае нам все еще нужно обновить раза $8$ $\frac{(n)(n+2)}{2}$

Merbs
источник

и I и II разрешимы с помощью #next_greater_element, который я объяснил здесь . но это немного сложнее, чем просто проблема, но перед решением вам нужно изучить следующий более важный элемент:

рассмотрим, что у нас есть вектор для каждого элемента из имя для элемента . теперь один раз запустите следующий больший алгоритм, начиная справа налево, но, кроме установки элемента в его следующего большего индекса элемента, вставьте в элементы, которые является их следующим большим элементом. Затем выполните итерацию по массиву слева направо, а затем где - размер вектора . и его потому что каждый следующий больший алгоритм равен а также повторение $A$ $S_i$ $i$ $i$ $A$ $S_i$ $i$ $B[i]=\sum_{j=0}^x (S_i[j]+1)$ $x$ $S_i$ $\Theta(n)$ $\Theta(n)$ $\Theta(n)$

вторая часть также сходна отметить , что мы можем получить значение элемента , самый правый в EDIT: мое решение является неправильным, кажется , что не имеют каких - либо решение $O(1)$ $o(n)$

Ali.Mollahoseini
источник