05.06.2013, 08:57
|
|
Аспирант
|
|
Регистрация: 05.03.2012
Сообщений: 62
|
|
Нахождение "середины" массива.
Не совсем по языку вопрос, скорее поиск алгоритма.
Возможно ли за O(N) найти число, которое было бы меньше ровно половины чисел из не отсортированного массива чисел, в котором четное количество элементов и никакие числа не равны?
Например, для массива [9,7,1,8] это число будет 7.5
Последний раз редактировалось zOdmin, 05.06.2013 в 09:02.
|
|
05.06.2013, 11:23
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,205
|
|
Сообщение от zOdmin
|
из не отсортированного массива чисел
|
Что мешает отсортировать тот массив?
|
|
05.06.2013, 15:59
|
|
Профессор
|
|
Регистрация: 11.09.2010
Сообщений: 8,804
|
|
Сообщение от ksa
|
Что мешает отсортировать тот массив?
|
Сложность алгоритма, большая чем O(N) ?
|
|
05.06.2013, 17:04
|
|
Аспирант
|
|
Регистрация: 05.03.2012
Сообщений: 62
|
|
Да, с сортировкой всё слишком просто. Думал, может всё же можно как-то за O(N) успеть.
В общем, задача "немного" упрощается, потому что может быть удастся использовать информацию из других итераций основного цикла. Самое смешное, что это реальная задача, а не забавы ради.
Короче, находить это число нужно для большого количества массивов. Каждый следующий массив получается из предыдущего путем таких манипуляций: сначала прибавляем 1 к первому элементу, потом 2 ко второму и т.д. К последнему элементу добавляем N. Предположим, что самый первый массив мы таки отсортировали (за NlogN действий или встроенной функцией) и нашли "среднее" число. Поможет ли нам это в нахождении "среднего" числа следующего массива?
|
|
05.06.2013, 17:24
|
Профессор
|
|
Регистрация: 16.05.2013
Сообщений: 229
|
|
походу все-таки можно
я сам в шоке
нужен алгоритм BFPRT
алгоритм дает верхнуюю границу сложности поиска i-го порядкового элемента в массиве из n элементов следующего вида -- 103*n/18
в случае вашей задачи - находим за линейное время элемент n/2
- находим за линейное время элемент n/2+1
- берем среднее арифметическое этих двух элементов
people.csail.mit.edu/rivest/pubs/BFPRT72.pdf -- вроде бы оригинал статьи об алгоритме
ru.wikipedia.org/wiki/BFPRT-Алгоритм -- версия в википедии
-----------------------------------------------------------------
P.S.
я протупил
описал как найти медиану
надо найти только элемент n/2 или n/2+1 в зависимости от направления сортировки
Последний раз редактировалось mta88, 05.06.2013 в 17:31.
|
|
05.06.2013, 17:26
|
Профессор
|
|
Регистрация: 16.05.2013
Сообщений: 229
|
|
а с практической точки зрения я б не заморачивался такими оптимизациями
n*log n более чем достаточно
|
|
05.06.2013, 17:35
|
|
Аспирант
|
|
Регистрация: 05.03.2012
Сообщений: 62
|
|
Сообщение от mta88
|
походу все-таки можно
я сам в шоке
нужен алгоритм BFPRT
|
Не подходит:
http://ru.wikipedia.org/wiki/BFPRT-Алгоритм
Цитата:
|
1. Список делится на подмножества элементов, по 5 элементов в каждом (кроме последнего подмножества). Число элементов в подмножествах может варьировать от 5 до 21 и должно быть в любом случае нечётным.
2. Каждое подмножество сортируется с помощью подходящего алгоритма сортировки.
|
Сообщение от mta88
|
а с практической точки зрения я б не заморачивался такими оптимизациями
n*log n более чем достаточно
|
Просто слишком много вычислений. В посте №4 я приблизился к сути реальной задачи. Сортировка внутри цикла выглядит не очень хорошо.
Последний раз редактировалось zOdmin, 05.06.2013 в 17:39.
|
|
05.06.2013, 17:54
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,103
|
|
Сообщение от zOdmin
|
найти число, которое было бы меньше ровно половины чисел из не отсортированного массива чисел, в котором четное количество элементов и никакие числа не равны?
Например, для массива [9,7,1,8] это число будет 7.5
|
Вариант ...
var arr = [9,7,1,8], a = [1, 2, 3, 4, 5, 6, 7, 8];
function get(arr)
{
var m = Math.max(arr[0],arr[1]) , n = Math.min(arr[0],arr[1]);
for (var i=0; i<arr.length; i=i+2) {
var min = Math.min(arr[i],arr[i+1]),
max = Math.max(arr[i],arr[i+1]);
if (max < m) m = max;
if (min > n) n = min;
} ;
return (n+m)/2
}
alert([get(arr),get(a)].join('\n'));
|
|
05.06.2013, 18:07
|
Профессор
|
|
Регистрация: 16.05.2013
Сообщений: 229
|
|
подходит, подходит
у алгоритма линейное время работы, это точно, поскольку его придумали академики лет 40 назад
|
|
05.06.2013, 18:32
|
|
Профессор
|
|
Регистрация: 11.09.2010
Сообщений: 8,804
|
|
рони,а теперь без встроенных функций )
|
|
|
|