Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Когда мы ранее ввели формулу вычисления определителя линейной алгебры, мы ввели обратное число: после того, как мы перечислим каждый элемент определителя, нам нужно использовать обратное число, чтобы определить положительный или отрицательный знак этого элемента. Если вы забыли студентов, вы можете вернуться к предыдущей статье, чтобы просмотреть:
Если вы его забудете, это не большая проблема.Концепция относительно проста, и я думаю, что скоро все смогут в ней разобраться.
В сегодняшней статье я хочу поговорить с вами об алгоритме обратных порядковых чисел, который также является очень классическим алгоритмическим вопросом, который часто появляется в вопросах на собеседованиях в крупных компаниях.
Давайте сначала рассмотрим определение обратного числа.Так называемое обратное число относится к тому, сколько пар чисел существует в массиве, так что число впереди больше, чем число сзади. Возьмем пример, предположим, что в данный момент есть массив: [1, 3, 2].
Для пары (3, 2), поскольку 3 предшествует 2 и 3 > 2, это означает, что (3, 2) — обратная пара. Количество всех обратных пар во всем массиве является обратным числом.
Из определения обратного порядкового номера нетрудно понять, что обратный порядковый номер на самом деле является индикатором, используемым для измерения степени порядка массива. Чем больше обратное число, тем хуже приращение массива. Если число инверсии равно 0, последовательность строго возрастает. Если инверсия массива длины n равна
, то это означает, что массив строго убывает, а обратный порядковый номер в этот момент самый большой.
Итак, как мы можем быстро решить обратное число?
решение грубой силы
Очевидно, что эту проблему можно решить насильственно.Нам нужно только обойти все пары, а затем судить, составляют ли они обратный порядок.Наконец, добавление количества всех пар обратного порядка является окончательным ответом.
Этот код очень прост и требует всего несколько строк:
inverse = 0
for i in range(1, 10):
for j in range(0, i):
if arr[j] > arr[i]:
inverse += 1
Это, конечно, возможно, но мы также можем легко обнаружить, что временная сложность этого процесса равна
, что часто для нас неприемлемо. Даже C++, который работает очень быстро, может выполнять масштабирование до n=1000 в секунду на одноядерном процессоре. Независимо от того, насколько он велик, время, затрачиваемое на его выполнение, резко возрастет, и в практических приложениях массив длиной более 1000 — просто обычное дело. Очевидно, нам нужно оптимизировать этот алгоритм и нельзя просто решить его перебором.
разделяй и властвуй
Мы можем попытаться решить эту проблему, используя алгоритм «разделяй и властвуй».
Для массива arr мы пытаемся разделить его на две половины, например, текущий arr [32, 36, 3, 9, 29, 16, 35, 73, 34, 82]. После того, как мы разделим его на две половины, это [32, 36, 3, 9, 29] и [16, 35, 73, 34, 82]. Пусть подмассив левой половины будет A, а подмассив правой половины будет B. Очевидно, что A и B являются подзадачами исходной задачи, мы можем предположить, что результаты подзадач A и B могут быть решены рекурсией.
Итак, вопрос в том, как построить результат arr из результатов подзадач A и B? Иными словами, как мы можем получить ответ на первоначальный вопрос, разделяя и преодолевая подзадачи?
Прежде чем ответить, давайте проанализируем текущую ситуацию. Когда мы разделяем массив arr на две части AB, обратное число всего arr становится тремя частями. Это обратное число между массивами A, обратное число между массивами B и обратное число между двумя массивами AB, то есть пара обратных чисел с одним элементом в A и одним элементом в B. Проанализируем его еще раз, и мы обнаружим, что обмен элементами в массиве A повлияет только на обратное число между массивами A, и не повлияет на обратное число, образованное между B и AB. Потому что элементы в A находятся впереди всех элементов в массиве B, даже если они меняются местами.
Возьмем пример:
Предположим, что arr=[3, 5, 1, 4], тогда A=[3, 5], B=[1, 4]. Для arr его обратное число равно 3, то есть (3, 1), (5, 1) и (5, 4). Для A его обратное число равно 0, и обратное число B также равно 0. Попробуем обменять позицию в B, после обмена B=(4, 1), в это время arr=[3, 5, 4, 1]. Тогда обратное число B становится равным 1, а обратное число A по-прежнему равно 0. Обратное число общего числа становится равным 4, а именно: (3, 1), (5, 1), (5, 4) и (4, 1).Очевидно, что новое дополнение к общему обратному числу - это B обмен элемент принес. Путем наблюдения мы также можем обнаружить, что для 3 и 5 в A порядок 1 и 4 в B не влияет на количество образуемых ими обратных чисел.
Как только вы поймете этот слой, остальное будет легко. Поскольку элементы в A и B не повлияют на результат друг друга, независимо от того, как поменяется порядок, мы можем безопасно использовать алгоритм «разделяй и властвуй» для решения проблемы. Давайте сначала предположим, что мы можем рекурсивно получить соответствующие обратные числа A и B. Тогда остается проблема найти все обратные пары A и B, которые занимают один элемент.
Давайте сначала отсортируем элементы в A и B. Перед этим мы проверили, что корректируем порядок элементов в A или B, не меняя количество обратных чисел в AB, и мы получили A и A с помощью рекурсии Количество обратных пар в B, поэтому после его сохранения мы можем отсортировать элементы в A и B. После того, как элементы в A и B упорядочены, мы можем использовать метод сортировки вставками, чтобы вставить элементы из A в B по очереди.
B: XXXXXXXXX j XXXXXXXXXXXX
/
ai
Как видно из приведенного выше рисунка, предположим, что мы положили
Этот элемент вставляется в положении j в массиве B. потому что раньше
Он расположен перед j элементами B, поэтому он составляет j перевернутых порядковых пар. мы для всех элементов в A
Найдите позицию j всех вставок в массиве B, а затем просуммируйте j.
Легко думать, что, поскольку элементы B упорядочены, мы можем найти положение элементов в A методом дихотомии. Но на самом деле есть лучший способ: мы можем выполнить сортировку и вставку AB за один шаг, то есть объединить два упорядоченных массива AB. В процессе слияния мы можем не только узнать позицию вставленного массива B, но и завершить сортировку массива, что кстати решает проблему сортировки A и B. Таким образом, весь шаг на самом деле является расширением сортировки слиянием.Хотя разница между всем кодом и сортировкой слиянием очень мала, вывод и мышление в этом процессе очень важны.
Если вы можете понять описанный выше процесс вывода, я думаю, что код не сложен для вас. Ничего страшного, если вы еще не до конца это поняли, с кодом, я уверен, вам будет легче понять. Без лишних слов давайте посмотрим на код:
def inverse_num(array):
n = len(array)
if n <= 1:
return 0, array
mid = n // 2
# 将数组拆分为二往下递归
inverse_l, arr_l = inverse_num(array[:mid])
inverse_r, arr_r = inverse_num(array[mid:])
nl, nr = len(arr_l), len(arr_r)
# 插入最大的int作为标兵，可以简化判断超界的代码
arr_l.append(sys.maxsize)
arr_r.append(sys.maxsize)
i, j = 0, 0
new_arr = []
# 存储array对应的逆序数
inverse = inverse_l + inverse_r
while i < nl or j < nr:
if arr_l[i] <= arr_r[j]:
# 插入A[i]的时候逆序数增加j
inverse += j
new_arr.append(arr_l[i])
i += 1
else:
new_arr.append(arr_r[j])
j += 1
return inverse, new_arr
На уровне кода приведенный выше код реализует сортировку слиянием, а также вычисляет обратное число. Вот почему многие люди сравнивают их, и почему мне лично так нравится этот вопрос. Две, казалось бы, не связанные между собой задачи можно решить с помощью почти одного и того же набора кода, и я должен вздохнуть с магией алгоритма. Именно благодаря этому мы, исследователи и изучающие алгоритмы, можем получать постоянный поток удовольствия.
Вот и все на сегодняшнюю статью, если вы чувствуете, что я что-то приобрел, пожалуйстаСканируйте код легкоОбратите внимание, ваша поддержка — моя самая большая мотивация.