|
Да, с сортировкой всё слишком просто. Думал, может всё же можно как-то за O(N) успеть.
В общем, задача "немного" упрощается, потому что может быть удастся использовать информацию из других итераций основного цикла. Самое смешное, что это реальная задача, а не забавы ради.
Короче, находить это число нужно для большого количества массивов. Каждый следующий массив получается из предыдущего путем таких манипуляций: сначала прибавляем 1 к первому элементу, потом 2 ко второму и т.д. К последнему элементу добавляем N. Предположим, что самый первый массив мы таки отсортировали (за NlogN действий или встроенной функцией) и нашли "среднее" число. Поможет ли нам это в нахождении "среднего" числа следующего массива?
|