LeetCode41, один вопрос, чтобы понять идеи на месте

алгоритм

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания


СегодняСтатья 21 из серии «Решение проблем LeetCode», Сегодня давайте рассмотрим тему, о которой люди мало говорят.

тема

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

Это кажется немного неудобным, поэтому позвольте мне кратко объяснить. Все мы знаем, что положительные целые числа — это целые числа, начинающиеся с 1, поэтому эта задача состоит в том, чтобы начать с 1, чтобы найти первый элемент, которого нет в массиве. Давайте посмотрим на следующий пример:

Пример 1:

Input: [1,2,0]
Output: 3

Пример 2:

Input: [3,4,-1,1]
Output: 2

Пример 3:

Input: [7,8,9,11,12]
Output: 1

Уведомление:

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

анализировать

Прежде чем мы это заметим, мы можем подумать, что эта проблема не так уж сложна, и легко придумать решение, но после этих двух ограничений это не так просто. Нам нужно перебрать массивСложность , как найти наименьший недостающий элемент? При этом нельзя применять дополнительные массивы, а можно использовать только хранилище постоянного уровня, очевидно, нельзя использовать различные вспомогательные массивы и контейнеры.

Трудно найти решение, если мы так много думаем, почему бы нам не прийтишаг за шагом.

Давайте сначала предположим, что без этих ограничений, какой метод следует использовать, проще всего придуматьСортировать. Мы сортируем массив, что удобно, когда массив отсортирован. Мы переходим от малого к большому, и легко определить, какие элементы появляются, а какие нет. Тогда легко найти наименьшее натуральное число, которого нет в массиве. Анализируя сортировку, мы можем обнаружить, что мы не использовали дополнительное пространство в этом процессе, и единственное, что не удовлетворяет условию, это то, что наша временная сложность равнавместо.

Записываем код:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums = sorted(nums)
        if len(nums) == 0 or nums[0] > 1:
            return 1
        
        mark = 1
        for i in nums:
            if i == mark:
                mark += 1
        
        return mark

В свою очередь, если мы гарантируем, что пространство можно использовать по желанию, но ограничим временную сложность, какие решения мы можем придумать?

Также должно быть легко разобраться, то есть ввести дополнительные контейнеры. Например, хэшсет. Сложность добавления, удаления, модификации и проверки хэшсета можно приблизительно считать постоянным уровнем. Нам нужно только один раз пройтись по массиву, вставить все элементы в хеш-набор, записать максимальное и минимальное значения элементов и, наконец, пройти интервал между минимальным и максимальным значениями, чтобы найти наименьший элемент, которого нет в набор хэшей. Для массива из n элементов мы можем легко доказать, что должны быть в состоянии найти натуральное число, которого нет в массиве, за n поисков.

Этот код тоже не сложно написать:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        st = set()
        if len(nums) == 0:
            return 1
        
        mini, maxi = 3e9, -3e9
        
        # 插入set当中维护
        for i in nums:
            st.add(i)
            mini = min(mini, i)
            maxi = max(maxi, i)
            
        # 从1开始找到第一个不在set当中的元素
        # 由于nums只有n个元素，我们可以可以在n次遍历当中找到
        for i in range(1, maxi):
            if i not in st:
                return i
            
        # 如果从1到maxi都存在，那么就放回maxi+1和1的最大值
        # 因为如果maxi小于1，那么上面的循环不会执行，所以要和1取最大值
        return max(maxi+1, 1)

in-place

Один из двух вышеперечисленных методов выполняет сортировку высокой сложности, а другой использует дополнительное хранилище. Похоже, это дилемма, нам нужно использовать хранилище, если мы не хотим сортировать, а если мы не хотим использовать хранилище, то нам нужно, чтобы элементы сортировались. Если мы внимательно проанализируем эти две ситуации, мы сможем найти суть проблемы: можем ли мы как-то получить лучшее из обоих миров?Без дополнительного хранилища можно гарантировать порядок элементов?? Если мы сможем найти способ, то эта проблема будет решена.

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

Так как же нам прорваться?

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

in-place — это не алгоритм, а идея. Причина его появления также очень проста, потому что, когда мы применяем контейнеры, такие как массивы, нам нужноЗапрос непрерывной памяти из памяти через операционную систему, который потребует выполнения ряда алгоритмов управления памятью, поэтому необходимозанимает много временииз. Поэтому в некоторых сценариях с высокой производительностью мы хотели бы максимально избегать операций с космическими приложениями.

Например, если мы хотим отсортировать массив, когда мы напрямую вызываем метод sorted, мы фактически копируем массив внутри функции, а окончательный возврат фактически является результатом скопированного массива после сортировки. То есть мыполучить новый массив, но элементы точно такие же, как и раньше. А если это in-place метод, то мы не будем создавать дополнительный массив, а модифицируем исходный массив.

Интерфейс не на месте не изменит исходное значение, что нам удобно для отслеживания изменений данных и отмены операций. Например, большое количество интерфейсов numpy и pandas в области машинного обучения Python по умолчанию не на месте, что и является причиной. На месте все наоборот, потому что оно напрямую изменит исходное значение, поэтому, если мы выполним его неправильно, его нельзя будет отменить, и исходные данные не могут быть восстановлены. Например, если мы отсортировали в неправильном порядке, мы, очевидно, хотим отсортировать его по убыванию, но случайно отсортируем его по возрастанию, после выполнения его нельзя будет восстановить. Но по сравнению с не на месте, егоМеньше времени и больше памяти.

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

Нам нужно разработать алгоритм на месте, который позволит нам определить существование элементов. Кроме того, ограничение в заголовке — это положительное целое число, и мы ищем первое положительное целое число, которое не появляется. Если длина массива равна n, то мы действительно можем заблокировать,Ответ должен быть между [1, n+1]. Причина также очень проста, потому что идеальная ситуация состоит в том, что n элементов в этом массиве ровно от 1 до n, так что мы переходим от 1 к n, и ответ равен n+1. В противном случае мы должны быть в состоянии найти ответ до перехода к n+1, так что в итоге ответ должен быть между [1, n+1]. Если мы сможем выписать этот интервал, фактически решение уже перед нами.

Поскольку ответ находится в середине интервала [1, n+1], нам нужно разработать метод на месте, тогда мы обычно можем думать, что можемПоместите число в соответствующий индекс. 1 ставится в нижнем индексе 1, а 0 ставится в 0.

Например [3, 1, 0, 5], получаем первый элемент 3, ставим его в позицию где он должен быть, то есть позицию 5, на этот раз снова ставим 5, т.к. длина массива, поэтому отбросьте его. Мы повторяем описанный выше процесс, В конце концов, мы получаем следующие данные: [0, 1, 5, 3], мы проходим массив и обнаруживаем, что позиция, которая не соответствует индексу, равна 5, что должно соответствовать Данных 2, поэтому 2 — ответ.

Алгоритм я придумал первым, почти из воздуха, без процесса вывода до и после. Позже, после идеи ассоциации на месте, я обнаружил, что скрытая идея на самом деле очень разумна. С идеей код действительно прост:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        # 因为是正整数，所以数组长度需要扩大1
        nums.append(0)
        
        for i in range(n):
            if i == nums[i]:
                continue
                    
            while True:
                # 不停地交换元素，直到范围超界或者是已经放好了为止
                # 需要考虑nums[i] 和 nums[nums[i]]相等的情况，这时候也不应该交换
                val = nums[i]
                if val > n or val < 0 or val == i or val == nums[val]:
                    break
                nums[i], nums[val] = nums[val], val
                
        
        for i in range(1, n+1):
            if i != nums[i]:
                return i
            
        return n+1

Напоследок разберем сложность этого алгоритма, почему мы ставим цикл while в цикл, а он все равноалгоритм?

Мы представили эту проблему раньше, когда ввели два указателя и линейки.Когда мы анализировали сложностьВы не можете просто посмотреть, сколько циклов, мы должны проанализировать его подробно. Мы хотим проигнорировать цикл и вернуться к сути проблемы. Суть цикла состоит в том, чтобы поставить каждый элемент в соответствующую позицию, общее количество элементов, которые нужно расположить, фиксируется на n, и позиция также фиксируется на n, и элемент имеет только одну позицию. Таким образом, мы можем поместить хотя бы один элемент в правильное положение за раз, поэтому вопрос в том, сколько раз нам нужно выполнить цикл, чтобы все элементы оказались на своих местах?

Я прошу это, каждый должен быть очень четким, по крайней мере, по одному, n всего, очевидно, не более n раз. Тогда давайте посмотрим на цикл while, каждый раз, когда он выполняется, разве это не просто добавление элемента? Внешний цикл используется только для перечисления элементов и не требует дополнительных вычислений, поэтому, конечно, этоалгоритм.

Наконец, официальная сложность сегодняшней темы - Hard.Сама тема не сложная, но сложность повышена из-за добавления множества ограничений. В сегодняшней теме не используются новые алгоритмы, это чисто проверка мышления и логики. Поэтому я думаю, что это очень чистый вопрос, просто потому, что он не использует новые алгоритмы или новые структуры данных, он должен проверить нашу способность анализировать и думать о проблемах. И многие задачи очень адресные, если вы не выучили соответствующий алгоритм раньше, вы не сможете этого сделать, поэтому с этой точки зрения эта задачаСправедливее и отлично подходит для интервью. Я договорился о встрече и могу задать кандидату этот вопрос, если в будущем появится возможность пройти собеседование.

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

В этой статье используетсяmdniceнабор текста

Категории