Превышен лимит памяти - Python - PullRequest
Новая
       8

Превышен лимит памяти - Python

0 голосов
/ 19 ноября 2018

Я использую код ниже для получения индексов двух чисел из списка ввода, чья сумма равна цели. 

import itertools

class Solution:
   def twoSum(self, nums, target):
        combs = set(itertools.combinations(enumerate(nums), 2))
        while combs:
           elem = combs.pop()
           if int(elem[0][1]) + int(elem[1][1]) == target:
               return [elem[0][0], elem[1][0]]

cls = Solution()
nums = [3,3]
lst = cls.twoSum(nums,6)
print(lst)

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

1 Ответ

0 голосов
/ 19 ноября 2018

Ну, потому что у нас не может быть массивов / последовательных блоков памяти больше, чем 10 ^ 6 или 10 ^ 7

Если у нас есть Размер многомерного массива уменьшится до Матрицы [1000] [1000], чтобы получить всего ~ 10 ^ 7 блоков

Itertools генерирует все возможные пары, которые могут быть экспоненциальными, и сохранение их в наборе будет определенно переполнено как во времени, так и в пространстве.

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

один из способов решения этой проблемы - хеширование,

Основная идея A + B = target, где A, B - элементы массива

поэтому мы поддерживаем хеш-таблицу с ключом = элементом и значением = индексом

и итерации, чтобы найти, присутствует ли B = target - A, в массиве, если найден, мы печатаем индекс (A, B) 

class Solution:
    def twoSum(self, nums, target):
        hashtable = dict() # key = number , value = index
        n = len(nums)
        lst = []
       for i in range(n):

           if(hashtable.get(target-nums[i],None) is None):
           # not found so update the hashtable
               hashtable[nums[i]] = i
           else:
           # pair found
               lst.append((hashtable[target-nums[i]],i))

        return lst

cls = Solution()

nums = [3,3]
lst = cls.twoSum(nums,6)

print(lst)
...