Информация об изменениях

Сообщение Re[2]: Online Majority Element In Subarray. Что-то я туплю от 15.09.2019 9:51

Изменено 15.09.2019 10:00 rg45

Re[2]: Online Majority Element In Subarray. Что-то я туплю
Здравствуйте, zubr, Вы писали:


Z>Нужна предподготовка данных. В данной задаче нужно создать необходимый класс в конструкторе, чтобы потом быстро обслуживать запросы.

Z>Например, можно создать трехмерный массив [from,to,threshold], что конечно очень дорого в плане создания, зато потом очень дешево делать запросы.
Z>Приведенная выше структура (трехмерный массив) это не решение, но скорее направление в сторону решения.

Третье измерение не требуется. С учетом условия: 2 * threshold > right — left + 1, искомое число должно занимать более половины позиций поддиапазона. Соответственно, такое число либо одно, либо отсутствует. Поэтому достаточно двумерной коллекции (массив карт или массивов переменной длины), хранящим половину квадратной матной матрицы, элементом которой является пара {число/количество вхождений} (-1/0 — для заведомо "пустых" поддиапазонов).
Re[2]: Online Majority Element In Subarray. Что-то я туплю
Здравствуйте, zubr, Вы писали:


Z>Нужна предподготовка данных. В данной задаче нужно создать необходимый класс в конструкторе, чтобы потом быстро обслуживать запросы.

Z>Например, можно создать трехмерный массив [from,to,threshold], что конечно очень дорого в плане создания, зато потом очень дешево делать запросы.
Z>Приведенная выше структура (трехмерный массив) это не решение, но скорее направление в сторону решения.

Третье измерение (threshold) не требуется. С учетом условия: 2 * threshold > right — left + 1, искомое число должно занимать более половины позиций поддиапазона. Соответственно, такое число либо одно, либо отсутствует. Поэтому достаточно двумерной коллекции (массив карт или массивов переменной длины), хранящим половину квадратной матной матрицы, элементом которой является пара {number/threshold} (-1/0 — для заведомо "пустых" поддиапазонов).