Big O из получить наибольшее количество

получили этот вопрос в последнее время:Big O из получить наибольшее количество

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

Например:

findLargest ([[10, 5, 3, 1], [9, 8, 7, 6], [11, 2, 1, 0]], 5) => [11, 10, 9, 8, 7]

findLargest ([[15, 5, 3, 1], [10, 8, 7, 6]], 3) => [15, 10, 8 ]

Сделайте это без копирования или изменения массивов (только что прочитанных из них). Оптимизация для временной сложности.

Я придумал это, но я не так доволен моим решением:

function findLargest(numberArrays, n) { 
    var results = []; 
    var pointers = []; 

    for (var x = 0; x < numberArrays.length; x++) { 
    pointers.push(0); 
    } 

    while (results.length < n) { 
    var subMaxes = []; 
    for (var i = 0; i < pointers.length; i++) { 
     var point = pointers[i]; 
     subMaxes.push(numberArrays[i][point]); 
    } 
    var max = Math.max.apply(null, subMaxes); 
    var indexOfMax = subMaxes.indexOf(max); 
    pointers[indexOfMax]++; 
    results.push(max); 
    } 
    return results; 
}

Я думаю, что это O (N^2) .... есть в любом случае сделать это в O (п)?

источник

2015-11-19 WinchenzoMagnifico

Это зависит от того, чувствуете ли вы, что «n» - это количество массивов или количество полных элементов во всех массивах. _Выбрав, что сами отдельные массивы уже отсортированы_, вы, вероятно, можете сделать _better_, чем «n», по количеству элементов, но может потребоваться n log n в терминах количества массивов. –

Это зависит от количества элементов в массивах. – djechlin

Сложность - это количество массивов, умноженное на количество элементов в самом длинном массиве. – Oleander

Вопрос может быть оформлена (и слегка переделан), как, Given a 2D array of dimension n x n, where each row is sorted in a decreasing order, find the largest k elements

Для крупнейших n элементов, временная сложность будет O(nlogn). Процедура k крупнейших элементов объясняется ниже:

Построить макс кучу первого элемента из каждой строки: сложность Время О (п)
Извлечение наибольший элемент из кучи, и вставьте элемент в кучу из строки, к которой принадлежит извлеченный элемент. Сложность времени - O (logn)
Повторяется при желаемом количестве элементов.

Таким образом, для итерации для извлечения наибольшего числа требуется время O (logn) с предварительной оплатой O (n).

Для извлечения k элементов, временная сложность описанного выше алгоритма является O(klogn)

источник

2015-11-19 19:11:02 therainmaker

Извлечение наибольшего числа является постоянным, потому что оно находится на вершине кучи, нет? Вставки - это то, что вызывает 'O (logn)' –

. Как бы вы реализовали это без изменения массивов? Я использовал индекс, чтобы отслеживать, где я был в каждом массиве. Как вы выполняете часть на шаге 2 --- «вставьте элемент в кучу из строки, к которой принадлежит извлеченный элемент» - как сохранить ссылку на какой из них она принадлежит? – WinchenzoMagnifico

@WinchenzoMagnifico: При использовании вашей пары кучи , где первое - это значение объекта, а второе - индекс строки, к которой он принадлежит. – therainmaker

Merge все массивы в единый массив. Это занимает время O (n).
Используйте медиану алгоритма медианов, чтобы найти k-й наибольший элемент в новом массиве. Вовремя.
Перемещение массива и захват всех элементов, больше или равных этому элементу. Это занимает время O (n).

Этот алгоритм работает в O (n) времени.

источник

2015-11-19 20:46:48 nietsnegttiw

Big O из получить наибольшее количество

ответ

Смежные вопросы