Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCodeВ 50-й статье поговорим о поиске из 81 вопроса в Rotated Sorted ArrayII в LeetCode.
Его официальная сложностьMedium, 1251 лайк, 470 отклонений и проходной балл 32,8 %. Судя по проходимости, этот вопрос относится к более сложным вопросам средней сложности и, правда, является небольшой проверкой мышления.
смысл названия
Предположим, у нас есть упорядоченный массив с повторяющимися элементами, мы случайным образом выбираем позицию, чтобы разделить его на две половины, а затем меняем порядок двух частей и объединяем их в новый массив. Теперь, получив цель, попросите вернуть логический результат,Указывает, находится ли цель в массиве.
Образец
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Если вы прочитаете LeetCode или эту тему по порядку, вы обнаружите, что мы уже решали очень похожую задачу. это33 вопроса от LeetCode, Поиск в отсортированном массиве с чередованием I. Однако разница в том, что в значении вопроса 33 четко указано, что элементы в массиве не содержат повторяющихся элементов, кроме того, смысл двух вопросов совершенно одинаков.
LeetCode 33, используя метод деления пополам в массиве, который не удовлетворяет делению пополам.
Приведет ли такая небольшая разница к изменению решения?
отвечать
Ответ, конечно, да, иначе вопрошающий может удалиться.
Вопрос в том, где проблема?
Не волнуйтесь, давайте сначала вспомним практику в вопросе 33. Мы использовали один из самых простых глупых методов в то время, который былСначала найдите положение усечения массива по дихотомии. Затем восстановите исходный массив через усеченную позицию и найдите ее возможную позицию в соответствии с размером нашей цели.
Но в текущей задаче эта идея не работает. Причина, по которой это не работает, очень проста, потому чтоповторяющиеся элементыПрисутствие.
Например: [1, 3, 1, 1, 1, 1, 1, 1]
Когда мы выполняем бинарный поиск, мы обнаруживаем, что mid равно 1, а 1 слева равно, мы простоНе могу сказать, находится ли точка усечения слева или справа от середины, о бинарном поиске не может быть и речи.
Конечно, мы можем сделать шаг назад и использовать метод обхода, чтобы найти точку сегментации, но в этом случае, почему бы нам не перейти непосредственно к поиску ответа? В любом случае, это уже O(n) сложности. Так что это не работает, мы хотим сохранить сложность на уровне
Вы должны найти другие пути.
Идеи и решения часто берутся не из воздуха, и нам необходимо провести глубокий анализ проблемы. В этом вопросе наша проблема ясна и проста. Это упорядоченный массив с переставленными частями, но мы не уверены, какова их длина. Поскольку мы в конечном счете надеемсяПоиск ответов через дихотомию, поэтому мы можем придумать два случая в зависимости от того, больше ли половины замененных элементов.
Я показываю эти две ситуации графически:
То есть нашТочка разделения может находиться в первой половине массива или во второй половине, наш подход к этим двум случаям отличается.
Сначала рассмотрим первый случай: первая половина массива упорядочена, а вторая половина усечена. Если целевой диапазон находится в первой половине, мы можем отбросить вторую половину и напрямую разделить первую половину. В противном случае нам нужно отбросить первую половину и повторить процесс во второй половине. Мы можем думать о второй половине как о совершенно новой проблеме, и ее также можно разделить на два случая, подобно рекурсии.
Давайте посмотрим на второй случай.Вторая половина второго случая такая же, как и первая половина первого случая.Все они упорядоченные элементы, и мы можем прямо разделить их на два. Первая его половина такая же, как и вторая половина первого случая, мы не можем судить, и нам нужно продолжить два пункта.
То есть мыРазделение пополам может быть выполнено только для отсортированных массивов, если текущий массив имеет сегменты и не упорядочен в целом, то разбиваем его. После расщепления всегда можно найти упорядоченную деталь, а если не найдешь, то продолжить расщепление. Поскольку существует только одна точка сегментации, независимо от текущего массива, после однократного разделенияДолжна быть возможность найти хотя бы один сегмент, который находится в порядке.
В этом легко разобраться, это очень похоже на рекурсию, но на самом деле она по-прежнему дихотомична по своей природе. Код написать несложно, но есть еще одна проблема, которая не решена, а именно, когда nums[m] = nums[l], как мы судим, какой это случай?
Ответ заключается в том, что нет никакого способа судить, возможны обе ситуации, и нет хорошего решения для этой ситуации.Решение, которое я придумал, состоит в том, чтобы переместить l на одно место справа, что эквивалентноотброшен крайний левый номер. Суммируем эти идеи, и выходит код:
class Solution:
def search(self, nums: List[int], target: int) -> bool:
l, r = 0, len(nums)-1
while l <= r:
m = (l + r) >> 1
if nums[m] == target:
return True
if nums[l] == nums[m]:
l += 1
continue
if nums[l] < nums[m]:
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
else:
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
return False
Суммировать
На этом наше решение этой проблемы закончилось. В конце вопроса человек, задавший вопрос, оставил нам вопрос.По сравнению с 33 вопросами решение этого вопроса менее точное.Изменится ли временная сложность??
На первый взгляд мы используем ту же дихотомию, поэтому сложность также находится на логарифмическом уровне, а сложность задачи не изменилась. Но на самом деле это не так, давайте рассмотрим наихудший сценарий,Предположим, что все значения в массиве равны. В это время деление пополам не будет работать и в конечном итоге выродится в линейное перечисление O (n), которое станет сложностью O (n). Конечно, в большинстве случаев этого не происходит. Таким образом, наихудшая сложность алгоритма вырождается до O(n), а средняя сложность по-прежнему равна O(logN).
Если вам понравилась эта статья, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста