Блог

Итак, в настоящее время у меня есть вопрос, который я пытаюсь решить:

• Учитывая массив из L различных целых чисел, которые все > 0, найдите, есть ли четыре уникальных целых числа, которые решают следующее уравнение >a^2 b — c^2 — d = 0

Я должен решить эту проблему со временной сложностью O(n^2).

Это моя нынешняя неудачная попытка решить проблему:

Сначала я переставляю уравнение, чтобы сделать a^2 b = c^2 d, затем инициализирую хэш-карту. Я использую вложенный цикл for для получения пар элементов. Я сохраняю сумму первого элемента в квадрате второй элемент. Затем я проверяю, есть ли он в хэш-карте. Если это так, я затем возвращаю true, так как нашел другую отличную пару, иначе, если нет, я добавляю ее в хэш-карту.

 def solution(arr, n):
  
    Hash = {} # Introduce a hash map
      
    # Create a double for loop
    for i in range(n - 1):
        for j in range(i   1, n):
            eqt = arr[i]* arr[i]   arr[j] # Take the sum
 
            if eqt in Hash.keys():
                # Return true as another pair has been found
                print('Found')
                return True
            else:
                # Sum isnt in hash so store it
                Hash[eqt] = (arr[i], arr[j])
    return False
 

Это решение, по-видимому, работает для упорядоченных массивов, но когда это не так, оно терпит неудачу
, т. е.: оно работает для [1,2,3,4,5,6,7] => получение (1, 6) и (2, 3)
, но не работает для [7,6,5,4,3,2,1].

Любое руководство или помощь будут высоко оценены, спасибо.

Проблема заключается в диапазоне переменной внутреннего цикла, j . Он смотрит только после i ; но он также должен смотреть все значения (кроме i th) в arr , а не только после i .

Итак, исправить это

 def solution(arr, n):

    Hash = {} # Introduce a hash map

    # Create a double for loop
    for i in range(n):
        for j in range(n):                   # main change is here!
            if i == j:                       # and here (excluding same element)
                continue

            eqt = arr[i]* arr[i]   arr[j] # Take the sum

            if eqt in Hash:
                # Return False as another pair has been found
                print("Found")
                return False
            else:
                # Sum isnt in hash so store it
                Hash[eqt] = (arr[i], arr[j])
    return True
 

Некоторые другие изменения:

• Он должен вернуться False , я думаю, когда он найдет пару в хэше (согласно описанию проблемы, я понял это так)
• for i in range(n) вместо n-1 того, чтобы позволить ему также взглянуть на последнее значение; сложность в целом одинакова
• eqt in Hash вместо того, чтобы закончиться keys ; то же самое, но более питоническое

Тестирование:

 >>> solution([1,2,3,4,5,6,7], 7)
False
>>> solution([7,6,5,4,3,2,1], 7)
False
 

Чтобы обеспечить четкость пар, мы модифицируем if as (как упоминает @JoranBeasley):

 if eqt in Hash and not any(val in Hash[eqt] for val in (arr[i], arr[j])):
    ...
 

чтобы проверить, что ни одно из значений в данном кандидате, т. е. arr[i], arr[j] находится в уже найденной паре, т. е., Hash[eqt] .