pro.algorithms
Добрый день. Может кто подсказать, пожалуйста? Дан массив натуральных чисел А,
нужно найти такие пары индексов j > i: A[j] - A[i] = j - i за линейную сложность, используя хеширование
9 ответов
Если надо найти все, то либо квадрат (так как для массива 1,2,3,4,...,n будет n*(n-1)/2 пар). Либо переопределить лист) В начале arr.groupByIndexed{idx,val->val-idx to idx}. Потом переопределить лист) Тогда можно лист сделать за линию. Возвращать по индексу из него за logn
Если надо найти все, то либо квадрат (так как для ...
Так за n же решается
если ограничения на A[i] в рамках 1e6 то можно хеш функцию даже не делать а определить пустой массив размером в максимальный A{I}
Если надо найти все, то либо квадрат (так как для ...
За 1 проход по массиву: превращаем каждое его значение в хэш таблицу где ключ это A[i]-i, а значение - динамический массив из i. Если ещё где то будет такая же разность - получаем сразу доступ к ячейке с нужными элементами и выводим пары текущего индекса с теми что внутри уже есть. А в конец потом ещё i допишем
За 1 проход по массиву: превращаем каждое его знач...
Все пары - это квадрат
Все пары - это квадрат
Все проверки это квадрат. Но можно сделать не все проверки)
Все пары - это квадрат
А найти все равные все ещё за n
Дон
Кинг
Автор вопроса
За 1 проход по массиву: превращаем каждое его знач...
Да, так работает, спасибо. Только нужно итоговое количество пар разделить пополам, чтобы одни и те же пары не учитывать дважды.
Да, так работает, спасибо. Только нужно итоговое к...
Неа. Я сформулировал довольно четко: выводим пары текущего индекса с теми что уже доступны по ключу
Похожие вопросы
Обсуждают сегодня