Мне дали входной поток & два индекса (i & j), между которыми вам нужно рассчитать min, max & avg всех чисел. Какую структуру данных я должен использовать &, как мне рассчитать значения?max, min среднее значение входного потока
Практически любая структура данных будет в порядке, в зависимости от языка, конечно. В зависимости от языка список, вероятно, будет быстрее всего реализован. Вычисление min, max и average довольно просто - повторяйте ваши значения. Возьмите каждое значение и сравните его с текущими значениями min и max - если оно больше максимального или меньше, чем min, замените его, а затем добавьте значение в текущее значение для средних целей.
Очень простое решение для этого было бы использовать простые массивы.
Array 1: Введите данные для ввода только следующего индекса.
Массив 2: Сумма: сумма [я] = вход 1 + вход [2] + ... + вход [я]
Это позволяет СРЕДНЕМ быстро. O (1), но min и max в худшем случае все еще O (N).
Если вы хотите что-то еще, вы можете использовать segment tree и выполнять все запросы в O (log n). Вставка также становится O (log n)
Кажется довольно простым. Вы пытались решить это самостоятельно? Можем ли мы увидеть вашу попытку? – Dukeling
Было бы интересно, если бы была тонна пара индексов. Префикс суммы и RMQ, приятно. Однако для одной пары индексов это абсолютно тривиально. – harold