Решение O (n log n) (т. Е. Сортировка) состояло бы в том, чтобы отсортировать все значения данных, а затем запустить указатель от наименьшего к наибольшему при одновременном запуске указателя от наивысшего к наименьшему:
def findmatch(array n):
lo = first_index_of(n)
hi = last_index_of(n)
while true:
if lo >= hi: # Catch where pointers have met.
return false
if n[lo] = -n[hi]: # Catch the match.
return true
if sign(n[lo]) = sign(n[hi]): # Catch where pointers are now same sign.
return false
if -n[lo] > n[hi]: # Move relevant pointer.
lo = lo + 1
else:
hi = hi - 1
Решение сложности времени O (n) состоит в том, чтобы поддерживать массив всех встреченных значений:
def findmatch(array n):
maxval = maximum_value_in(n) # This is O(n).
array b = new array(0..maxval) # This is O(1).
zero_all(b) # This is O(n).
for i in index(n): # This is O(n).
if n[i] = 0:
if b[0] = 1:
return true
b[0] = 1
nextfor
if n[i] < 0:
if -n[i] <= maxval:
if b[-n[i]] = 1:
return true;
b[-n[i]] = -1
nextfor
if b[n[i]] = -1:
return true;
b[n[i]] = 1
Это работает, просто поддерживая знак для данной величины, каждую возможную величину от 0 домаксимальное значение.
Итак, если в любой точке мы найдем -12, мы установим b [12] в -1.Потом, если мы найдем 12, мы знаем, что у нас есть пара.То же самое для нахождения положительного числа первым, за исключением того, что мы устанавливаем знак в 1. Если мы находим два -12 в ряду, это все равно устанавливает b [12] в -1, ожидая, пока 12 сместит его.
в этом коде есть только особые случаи:
- 0 обрабатывается специально, так как нам нужно обнаружить его, несмотря на его несколько странные свойства в этом алгоритме (я рассматриваю это специально, чтобы не усложнять положительные и отрицательные случаи).
- низкие отрицательные значения, величина которых превышает наибольшее положительное значение, могут быть безопасно проигнорированы, поскольку совпадение невозможно.
Как и в большинстве хитрых «минимизация времени-сложности»Алгоритмы, у этого есть компромисс в том, что он может иметь более высокую сложность пространства (например, когда есть только один элемент в массиве, который оказывается положительным двух миллиардов).
В этом случае вы бывероятно, вернитесь к решению сортировки O (n log n), но, если вы знаете пределы заранее (скажем, если вы ограничиваете целые числа диапазоном [-100,100]), это может бытьмощная оптимизация.
В ретроспективе, возможно, более чистое решение могло бы выглядеть так:
def findmatch(array num):
# Array empty means no match possible.
if num.size = 0:
return false
# Find biggest value, no match possible if empty.
max_positive = num[0]
for i = 1 to num.size - 1:
if num[i] > max_positive:
max_positive = num[i]
if max_positive < 0:
return false
# Create and init array of positives.
array found = new array[max_positive+1]
for i = 1 to found.size - 1:
found[i] = false
zero_found = false
# Check every value.
for i = 0 to num.size - 1:
# More than one zero means match is found.
if num[i] = 0:
if zero_found:
return true
zero_found = true
# Otherwise store fact that you found positive.
if num[i] > 0:
found[num[i]] = true
# Check every value again.
for i = 0 to num.size - 1:
# If negative and within positive range and positive was found, it's a match.
if num[i] < 0 and -num[i] <= max_positive:
if found[-num[i]]:
return true
# No matches found, return false.
return false
Это делает один полный проход и частичный проход (или полный при отсутствии совпадения)в то время как оригинал сделал только частичный проход, но я думаю, что его легче читать, и ему нужен только один бит на число (найден положительный или не найден), а не два (нет, положительный или отрицательный найден).В любом случае, это все еще очень большая O (n) временная сложность.