Найти арифметическую прогрессию в массиве? Есть массив на 10**5 элементов , содержащие элементы из [0; 10**18] . Гарантируется , что найдутся 10**4 чисел, которые образуют арифметическую прогрессию . Вопрос , как найти эту самую прогрессию?
Найти арифметическую прогрессию в массиве? Есть массив на 10**5 элементов , содержащие элементы из [0; 10**18] . Гарантируется , что найдутся 10**4 чисел, которые образуют арифметическую прогрессию . Вопрос , как найти эту самую прогрессию?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для поиска арифметической прогрессии в массиве можно воспользоваться следующим методом:
Отсортировать массив по возрастанию.Пройтись по всем возможным парам элементов массива (i, j) и для каждой пары проверить, образуют ли они с неким третьим элементом также прогрессию. То есть, проверить, есть ли в массиве элемент i + (i - j), где i, j - индексы элементов массива.Если прогрессия найдена, то вывести эти три числа.Если прогрессия не найдена, увеличить j на 1 и вернуться к шагу 2.Этот метод имеет временную сложность O(n^2), что может быть эффективно при таком большом массиве.