Эффективный способ сравнения значения в массиве со всеми значениями до этого в массиве
У меня очень длинный массив чисел []. Мой алгоритм должен найти наименьший индекс j в числах [], при котором |numbers[j] - numbers[i]| <= x (случайная величина) или где |numbers[j] - numbers[i]| >= m - x (m другая переменная, больше x) и где i<j.
Теперь это мой алгоритм:
for (int j = 1; j < numbers.Length; j++)
{
for (int i = 0; i < j; i++)
{
long diff = Math.Abs(numbers[j] - numbers[i]);
if (diff <= x || diff >= m - x)
return j;
}
}
Можно ли это сделать более эффективно? Например, ввод с очень большими числами занимает у моего ноутбука около 36 секунд.
1 ответ:
Это можно сделать в O (nlogn) путем перебора массива и на каждом этапе добавления нового числа в сбалансированное дерево поиска.
Когда вы добавляете число, вы сначала ищете ближайшее число уже в дереве поиска. Если это число меньше целевой разницы, то вы нашли ответ.
Comments