Самый быстрый алгоритм для выбора пар чисел

Question

Вопрос: Задано N целых чисел [N < = 10^5], посчитайте полные пары целых чисел, которые имеют разность K. [K> 0 и K < 1e9]. Каждое из N целых чисел будет больше 0 и, по крайней мере, K от 2^31-1 (все может быть выполнено с 32-битными целыми числами).

1-я строка содержит N & K (целые числа). Вторая строка содержит N номеров набора. Все номера N гарантированы, чтобы быть отличным.

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

temp = input() 
temp = temp.split(" ") 
N = int(temp[0]) 
K = int(temp[1]) 
num_array = input() 
num_array = num_array.split(" ") 
diff = 0 
pairs= 0 
i = 0 
while(i < N): 
    num_array[i] = int(num_array[i]) 
    i += 1 
while(num_array != []):  
    j = 0 
    while(j < (len(num_array)-1)): 
     diff = abs(num_array[j+1] - num_array[0]) 
     if(diff == K): 
      pairs += 1 
     j += 1 
    del num_array[0] 
    if(len(num_array) == 1): 
     break 
print(pairs) 

Answer 1

Вы можете сделать это в приближенно минимаксного линейного времени с помощью следующей процедуры:

Таким образом, (п) Раствор O:

1. Для каждого числа х добавить его в хэш-набор H [ х]
2. для каждого числа х проверить ли хк в H, если да - добавить 1 ответить

или с помощью какой-то б alanced структура (например, дерево на основе набора) в O (nlgn)

Этого решения баз на предположении, что целые числа являются отчетливым, если они не нужно хранить число раз элемента было «добавлено в наборе "и вместо добавления 1, чтобы ответить - добавить продукт Н [х] * H [х + к]

Таким образом, в общем, вы берете некоторое HashMap H с„значение по умолчанию 0“

1. для каждого номер x карта обновления: H [x] = H [x] +1
2. Для каждого номера x добавить ответ H [x] * H [xk] (вы делаете не нужно проверять, находится ли он на карте, потому что, если это не так, H [xk] = 0)

и снова - решение с использованием хэш-карты O (n) и использование древовидной карты O (nlgn)

Так данный набор numbesr а, а число к (решение для различных чисел):

H=set() 
ans=0 
for a in A: 
    H.add(a) 
for a in A: 
    if a-k in H: 
    ans+=1 
print ans 

или короче

H=set(A) 
ans = sum(1 for a in A if a-k in H) 
print ans 

Answer 2

Используйте словарь (хэш-карту).

Шаг 1: Заполните словарь D всеми элементами массива. Шаг 2: Вводят слова всех A [i] + k в словаре.

Dictionary<int> dict = new Dictionary<int>(); 
foreach (int n in num_array) do dict.Add(n); 
int solitions = 0; 
foreach (int n in num_Array) do 
    if dict.contains(n+k) 
    solutions += 1; 

Заполнение словаря - O (1), поиск - O (1). Для каждого элемента массива это O (n). Это так быстро, как только можно.

Извините, но вы должны перевести его на python.

EDIT: та же идея, что и предыдущая. Извините, что разместите дубликат. Слишком поздно удалить мой дубликат, я думаю.