Тесты по алгоритмизации и программированию с ответами

Давайте сначала разработаем подход с оптимальным временем наихудшего случая.
Нам нужно сравнить числа. Чтобы увидеть. Есть ли у них свои противоположности в массиве. Тривиальное решение сравнения всех чисел имеет последовательное время O(N^2). Большое количество сравнений должно предполагать попытку установить оператор полного порядка. Который позволяет использовать сортировку для решения задачи. Если мы определим оператор сравнения. Который помещает все экземпляры числа сразу после всех экземпляров его противоположности. У нас будет ровно пара последовательных противоположных чисел для каждого числа. Которое имеет свою противоположность в массиве.

Пример того. Чего мы хотим достичь:

Array: -7 4 -3 2 2 -8 -2 3 3 7 -2 3 -2 Sorted: -2 -2 -2 2 2 -3 3 3 4 -7 7 -8 

Мы видим, что после нашего специального метода сортировки мы имеем [-2, 2], [-3, 3] и [-7, 7] комбинаций. Происходящих последовательно ровно один раз. Реализация этого сравнения проста и может быть реализована следующим образом.

FUNCTION compare(a, b) IF a != b and a != -b RETURN abs(a) abs(b) ELSE RETURN a b 

Если числа не равны или противоположны. Мы сортируем их по абсолютному значению. Но если они равны. Мы сортируем их по знаку. Наконец, решение. Основанное на этом. Теперь очень просто:

FUNCTION find_numbers_with_opposites(numbers) answer = List sorted_numbers = sort_by(numbers. Compare) FOR n IN [1..sorted_numbers.length()] IF sorted_numbers[n] > 0 AND sorted_numbers[n - 1] == -sorted_numbers[n] answer.push(n) END IF END FOR RETURN answer 

Эта реализация имеет наихудший случай сложности выполнения O(N log N). При этом алгоритм сортировки является узким местом.

Оптимальная средняя временная сложность случая O(N) может быть достигнута с помощью хэш-таблиц. Мы сопоставляем числа с их абсолютными значениями и проверяем. Есть ли их противоположности уже в хэш-таблице.

FUNCTION find_numbers_with_opposites(numbers) table = HashTable answer = List FOR number IN numbers IF number == 0 CONTINUE END IF key = abs(number) IF key not in table table[key] = number ELSE IF table[key] = -number answer.push(key) table[key] = 0 END IF END FOR 

Мы меняем значение в таблице на то. Что никогда не будет равно ни одному из чисел в массиве. Поэтому мы не возвращаем повторяющиеся результаты из повторяющихся совпадений.

Все операции HashTable имеют среднюю временную сложность O(1). И наша сложность является результатом выполнения операций N раз.