Найдите большее число форм "я" в левой части и меньшее число форм "я" в правой части

#algorithm #data-structures

#алгоритм #структуры данных

Вопрос:

Рассмотрим массив a n целых чисел, проиндексированных от 1 до n .

Для каждого индекса i , такого что 1<i<n , определите:

count_left(i) = количество индексов j такое, что 1 <= j < i и a[j] > a[i] ;
count_right(i) = количество индексов j такое, что i < j <= n и a[j] < a[i] ;
diff(i) = abs(count_left(i) - count_right(i)) .

Проблема в том, что для данного массива a найдите максимально возможное значение diff(i) for 1 < i < n .

Я получил решение методом грубой силы. Кто-нибудь может дать лучшее решение?

Ограничение: 3 < n <= 10 ^ 5

Пример

 Input Array: [3, 6, 9, 5, 4, 8, 2]
Output: 4
Explanation:
diff(2) = abs(0 - 3) = 3
diff(3) = abs(0 - 4) = 4
diff(4) = abs(2 - 2) = 0
diff(5) = abs(3 - 1) = 2
diff(6) = abs(1 - 1) = 0
maximum is 4.

1. «Грубая сила» несколько неизбежна, поскольку вы ничего не знаете о числах в массиве, вы должны изучить их все. Но какова была сложность вашего алгоритма? Я могу представить алгоритм с линейной временной сложностью, а другой — с квадратичной временной сложностью, и я бы назвал их обе грубой силой.

2. Мое решение TC таково O(n ^ 2) . Можете ли вы дать линейное решение TC?

3. Как i = 2 ==> 3 or i = 3 ==> 4 были получены подобные результаты?

4. i = 2 означает [i] = 6. Для левой части n1 = количество элементов левой стороны (от 1 до i — 1) больше, чем [i]. Итак, n1 = 0. Для правой стороны n2 = количество правой стороны (от i 1 до n) меньше, чем [i]. Итак, n2 = 3. Абсолютная разница равна 3

5. Описание проблемы неясно. Пожалуйста, предоставьте разъяснения.

Ответ №1:

O (nlogn) подход:

Пройдите по массиву слева направо и добавьте каждый элемент в расширенное двоичное дерево поиска (RB, AVL и т. Д.), содержащее поля размера поддерева, начального индекса и поля временного ранга. Итак, сразу после добавления мы знаем ранг элемента в текущем состоянии дерева.

 lb = index - temprank

это количество оставшихся больших элементов — запомните его в temprank поле.

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

 rs = finalrank - temprank

— количество правильных меньших элементов. Теперь просто получите абс разницы lb и rs

 diff = abs(lb - rs) = abs(index - temprank - finalrank   temprank ) = 
      abs(index - finalrank)

Но… мы видим, что нам temprank это вообще не нужно.
Более того — нам не нужно двоичное дерево!

Просто выполните сортировку пар (element; initial index) по ключу элемента и получите максимальную абсолютную разницу new_index - old_index (за исключением старых индексов 1 и n)

 a      3, 6, 9, 5, 4, 8, 2
old       2  3  4  5  6    
new       5  7  4  3  6
dif       3  4  0  2  0

Код Python для проверки концепции

 a = [3, 6, 9, 5, 4, 8, 2]
b = sorted([[e,i] for i,e in enumerate(a)])
print(b)
print(max([abs(n-o[1]) if 0<o[1]<len(a)-1 else 0 for n,o in enumerate(b)]))