Космическая сложность словаря python

Это вопрос по литкоду

https://leetcode.com/problems/find-the-duplicate-number/< /а>

Вот говорят:

Вы не должны изменять массив (предположим, что массив доступен только для чтения). Вы должны использовать только константу, O(1) дополнительное пространство. Ваша сложность во время выполнения должна быть меньше O(n^2). В массиве есть только одно повторяющееся число, но оно может повторяться более одного раза.

Итак, в моем коде я создаю словарь, используя Collection в python.

Как мой код удовлетворяет этой строке. Вы должны использовать только константу, дополнительный пробел O (1). и что они подразумевают под этой строкой, они понимают космическую сложность. Ниже приведен мой код, который очищает все тестовые файлы.

from collections import Counter 

class Solution:
    
    def findDuplicate(self, nums: List[int]) -> int:
        
        dict1=Counter(nums)
        
        for i in dict1:
            if(dict1[i]>1):
                return(i)

Пожалуйста помоги. Заранее спасибо.


python-3.x python algorithm space-complexity
person PARTH DUBEY    schedule 29.07.2020    source источник
comment
Подсказка: попробуйте найти решение, как если бы у вас была только одна переменная типа int для хранения данных.   -  person Marat    schedule 30.07.2020

Ответы (3)


arrow_upward
1
arrow_downward

Как правило, словарь всегда имеет пространственную сложность O(N), потому что это зависит от количества элементов вашего массива.

Пространственная сложность O(1) означает, что у вас одинаковое количество указателей независимо от размера массива. Например, если вы используете логическую переменную в своем алгоритме поиска, чтобы получить дубликат, это будет означать O(1).

Примечание:

Другое дело сложность времени выполнения, которая в случае со словарем составляет O(1), так как они основаны на хэш-таблицах, где вам нужен только ключ, чтобы получить значение. Наоборот, чтобы найти конкретное значение в списке, сложность выполнения составляет O(N), так как в худшем случае вам придется перебирать все элементы.

person David Duran    schedule 29.07.2020
comment
Не могли бы вы уточнить пространственную сложность O (1) ? - person PARTH DUBEY; 29.07.2020
comment
Я уточнил немного больше. По сути, это означает, что вы можете использовать в своем алгоритме только переменную (например, логическую). - person David Duran; 29.07.2020

arrow_upward
1
arrow_downward

Словари занимают пространство O(n), поэтому ваше решение занимает пространство O(n) и нарушает требования к пространству O(1).

Это старая проблема LeetCode, когда внимание LeetCode было сосредоточено на собеседованиях при приеме на работу, где такие требования могут возникать и обсуждаться (и раньше обсуждались на форуме LeetCode). Это никогда не применялось системой LeetCode, поэтому ваше решение принимается, несмотря на нарушение требований. К настоящему времени LeetCode ориентирован на конкуренцию и стал таким же, как и любой другой сайт, посвященный проблемам кодирования: важно только то, будет ли принято ваше решение, а теперь как. Они все еще не (не могут?) применять такие требования к пространству, и я думаю, что их новые вопросы больше не требуют чего-то подобного. Я скучаю по старым денькам.

person superb rain    schedule 29.07.2020
comment
Да, это хорошая задача относительно сложности. Это не так просто, как современные проблемы, где это уже не имеет значения. - person David Duran; 29.07.2020

arrow_upward
1
arrow_downward

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

class Solution:
    def findDuplicate(self, nums):
        lo, hi = 0, len(nums) - 1
        mid = (lo + hi) // 2
        while hi - lo > 1:
            count = 0
            for num in nums:
                if mid < num <= hi:
                    count += 1
            if count > hi - mid:
                lo = mid
            else:
                hi = mid
            mid = (lo + hi) // 2
        return hi

использованная литература

  • Дополнительную информацию можно найти на доске обсуждений. Существует множество общепринятых решений с различными языки и пояснения, эффективные алгоритмы, а также асимптотические время/пространство анализ сложности1, 2 там.
person Emma    schedule 29.07.2020