Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 05.06.2013, 08:57
Аватар для zOdmin
Аспирант
Отправить личное сообщение для zOdmin Посмотреть профиль Найти все сообщения от zOdmin
 
Регистрация: 05.03.2012
Сообщений: 62

Нахождение "середины" массива.
Не совсем по языку вопрос, скорее поиск алгоритма.

Возможно ли за O(N) найти число, которое было бы меньше ровно половины чисел из не отсортированного массива чисел, в котором четное количество элементов и никакие числа не равны?

Например, для массива [9,7,1,8] это число будет 7.5

Последний раз редактировалось zOdmin, 05.06.2013 в 09:02.
Ответить с цитированием
  #2 (permalink)  
Старый 05.06.2013, 11:23
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 14,205

Сообщение от zOdmin
из не отсортированного массива чисел
Что мешает отсортировать тот массив?
Ответить с цитированием
  #3 (permalink)  
Старый 05.06.2013, 15:59
Аватар для danik.js
Профессор
Отправить личное сообщение для danik.js Посмотреть профиль Найти все сообщения от danik.js
 
Регистрация: 11.09.2010
Сообщений: 8,804

Сообщение от ksa
Что мешает отсортировать тот массив?
Сложность алгоритма, большая чем O(N) ?
Ответить с цитированием
  #4 (permalink)  
Старый 05.06.2013, 17:04
Аватар для zOdmin
Аспирант
Отправить личное сообщение для zOdmin Посмотреть профиль Найти все сообщения от zOdmin
 
Регистрация: 05.03.2012
Сообщений: 62

Да, с сортировкой всё слишком просто. Думал, может всё же можно как-то за O(N) успеть.

В общем, задача "немного" упрощается, потому что может быть удастся использовать информацию из других итераций основного цикла. Самое смешное, что это реальная задача, а не забавы ради.

Короче, находить это число нужно для большого количества массивов. Каждый следующий массив получается из предыдущего путем таких манипуляций: сначала прибавляем 1 к первому элементу, потом 2 ко второму и т.д. К последнему элементу добавляем N. Предположим, что самый первый массив мы таки отсортировали (за NlogN действий или встроенной функцией) и нашли "среднее" число. Поможет ли нам это в нахождении "среднего" числа следующего массива?
Ответить с цитированием
  #5 (permalink)  
Старый 05.06.2013, 17:24
Профессор
Отправить личное сообщение для mta88 Посмотреть профиль Найти все сообщения от mta88
 
Регистрация: 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.
Ответить с цитированием
  #6 (permalink)  
Старый 05.06.2013, 17:26
Профессор
Отправить личное сообщение для mta88 Посмотреть профиль Найти все сообщения от mta88
 
Регистрация: 16.05.2013
Сообщений: 229

а с практической точки зрения я б не заморачивался такими оптимизациями
n*log n более чем достаточно
Ответить с цитированием
  #7 (permalink)  
Старый 05.06.2013, 17:35
Аватар для zOdmin
Аспирант
Отправить личное сообщение для zOdmin Посмотреть профиль Найти все сообщения от zOdmin
 
Регистрация: 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.
Ответить с цитированием
  #8 (permalink)  
Старый 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'));
Ответить с цитированием
  #9 (permalink)  
Старый 05.06.2013, 18:07
Профессор
Отправить личное сообщение для mta88 Посмотреть профиль Найти все сообщения от mta88
 
Регистрация: 16.05.2013
Сообщений: 229

Цитата:
не подходит
подходит, подходит
у алгоритма линейное время работы, это точно, поскольку его придумали академики лет 40 назад
Ответить с цитированием
  #10 (permalink)  
Старый 05.06.2013, 18:32
Аватар для danik.js
Профессор
Отправить личное сообщение для danik.js Посмотреть профиль Найти все сообщения от danik.js
 
Регистрация: 11.09.2010
Сообщений: 8,804

рони,а теперь без встроенных функций )
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Выбор из массива трех элементов sonntagausgang Общие вопросы Javascript 2 26.05.2013 02:59
Нужен цикл для создания огромного массива apish Общие вопросы Javascript 2 20.09.2012 16:10
Сортировка массива по ключу RazZzeR Элементы интерфейса 9 21.07.2012 19:31
Можно ли как для произвольного массива создавать вызовы функций , имеющих на входе kefi Общие вопросы Javascript 3 17.04.2009 16:53
вставка элементов массива в текстовую форму по клику olezyk Общие вопросы Javascript 3 21.03.2009 22:01