Предположим, что у нас есть несортированный массив, состоящий из целых чисел. У нас также есть 2 заданных целых числа L и M. Наша задача - вычислить количество всех пар (i, j), которые обладают следующим свойством: L < = A [j] -A [i] < = M.Разница элементов 1 несортированного массива в заданном интервале
Помимо очевидного алгоритма грубой силы, который проверяет все возможные пары сложности (O (n^2)), существует ли более быстрый способ решить эту проблему?
Я предполагаю, что вам просто нужно подсчитать количество различных пар, потому что иначе вы не можете надеяться на лучшую в худшем случае сложность, чем O (n^2).
Вы можете отсортировать массив в O (nlogn), отслеживая исходные индексы массива.
Затем просто сканируйте отсортированный массив и поддерживайте два указателя таким образом, чтобы все элементы между индексами, на которые они указывают, имели абсолютную разницу в диапазоне [L, M]. Эта часть может быть выполнена в линейном времени.
'Эта часть может быть выполнена в линейном времени.', А не тривиально (я не вижу способа сделать это как минимум три). Рассмотрим [1,2,3,4, ..., n] с 'L = 0, M = k> 1' вам нужно будет идти туда и обратно с обоими указателями (чтобы получить, например, (1,4) и затем назад (2,3), заставляя его быть квадратичным - если у вас есть какой-то трюк, чтобы предотвратить его и дать жесткий колпачок по количеству возвращающихся назад. – amit
@amit, скажем L = 0, M = 4. вы делаете указатель lo, hi указывать на 1 и продолжать увеличивать hi до тех пор, пока A [hi] -A [lo] <= 4. Update totalCount + = 4C2. Теперь увеличивайте и снова проверяйте до какой точки hi может идти, скажем, new lo = 2, hi = 8. Обновить totalCount + = (6C2 - 2C2), потому что 2C2 уже подсчитаны. (отсутствует что-нибудь?) –
Думаю, что у меня есть. Вам нужно несколько минут, чтобы подумать об этом, но выглядит хорошо для меня. + 1, и спасибо за объяснение. – amit
Определение количества таких пар может быть выполнено в O(nlogn) путем поддержания order statistics trees.
for each element x:
find x-L (or closest and higher element) in the tree. Let its index be i1.
finx x-M (or closest and smaller element) in the tree. Let its index be i2.
element x is part of i2-i1+1 pairs where x is the higher from the prefix of the array.
add this value to the sum.
Repeat for x+L,x+M
add x to the tree.
Это O(nlogn), каждое добавление и поиск O(logn). Это делается n, поэтому общая сумма O(nlogn).
Нижняя граница сложности: Это не может быть сделано лучше, чем O(nlogn) по алгебраической модели дерева, поскольку это позволит решить element distinctness problem в Omega(nlogn), который, как известно, невозможно.
Таким образом, проблема заключается в Omega(nlogn) по этой модели.
В худшем случае, размер вашего вывода равен 'O (n^2)'. Рассмотрим массив '[1,1,1,1,1,1 ..., 1]', с 'L = M = 0'. Вам нужно вывести все пары, и это квадратично. Тем не менее, вы можете сделать это в 'O (f (n) + m)' где 'm' - размер вывода, а' f (n) 'находится в' o (n^2) '(малый o обозначение здесь), если это помогает, я могу попытаться что-то придумать. – amit