Эффективный способ сравнения значения в массиве со всеми значениями до этого в массиве



У меня очень длинный массив чисел []. Мой алгоритм должен найти наименьший индекс 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 секунд.

526   1  

1 ответ:

Это можно сделать в O (nlogn) путем перебора массива и на каждом этапе добавления нового числа в сбалансированное дерево поиска.

Когда вы добавляете число, вы сначала ищете ближайшее число уже в дереве поиска. Если это число меньше целевой разницы, то вы нашли ответ.

Comments

    Ничего не найдено.