Отметить верхние N элементов несортированного массива

Question

У меня есть несортированный массив (сгенерированных роликов), и я хочу выбрать верхние N его элементов (что тривиально с сортировкой и сокращением), но отметьте их сохраняя при этом порядок.

.: например

mark([1,2,3,4], 3) ==> [[1, false], [2, true], [3, true], [4, true]] 

mark([3,5,2,6,2], 3) ==> [[3, true], [5, true], [2, false], [6, true], [2, false]] 

Массив может содержать любые значения от 1 до, и быть любой длины, и количество отмеченных элементов является переменной.

Я мог бы жить с

mark([3,5,2,6,2], 3) ==> [[3, true], [5, true], 2, [6, true], [2, true]] 

(т.е. цифры, которые были бы отмечены ложные идти без опознавательных знаков), но я предпочел бы избежать этого.

Обязательным является то, что порядок массива остается неизменным.

Если верхние элементы повторяются (например, верхняя часть 3 из [6,6,6,6,6,6]), отметьте первые 3 элемента.

(N достаточно мала для сложности, не имеет большого значения.)

EDIT: Бонус точка: добавить параметр для переключения между «сверху» и режим «снизу».

Answer 1

Принятый в настоящее время ответа просматривает список входного т раз. Этот сканирует его дважды. O (n) vs O (n * m). Вам нужна структура данных кучи. Здесь он находится на Python.

import heapq 

def mark(data, n): 
    top = heapq.nlargest(n, ((value, index) for index, value in enumerate(data))) 
    indexes = set(value[1] for value in top) 
    return [[value, index in indexes] for index, value in enumerate(data)] 

print mark([1, 2, 3, 4], 3) 
print mark([3, 5, 2, 6, 2], 3) 

Выход:

[[1, False], [2, True], [3, True], [4, True]] 
[[3, True], [5, True], [2, False], [6, True], [2, False]] 

Answer 2

Если он достаточно мал для сложности не имеет значения: (psuedocode)

for(int m = 0; m < mark_count; m++) { 
    highest = MIN_INT; 
    highestindex = -1; 
    foreach i in array: 
     if array[i] > highest && is_unmarked(i) 
      highest = array[i] 
      highestindex = i; 
    mark(i) 
} 

EDIT: Если вы хотите, чтобы найти нижние вместо них, начать наш счетчик на MAX_INT и убедитесь, что значение в массиве меньше.

И если вы хотите примеры реализаций mark() и is_unmarked:

function mark(i) { 
    array[i] = [array[i], true]; 
} 

function is_unmarked(i) { 
    if (array[i] is array & array[i][1] == true) 
     return false; 
    return true; 
} 

(Не уверен, что ли is работает, как я ожидать, что это - но смысл ясен, я надеюсь)

Answer 3

Вы можете использовать алгоритм quick select с массивом индексов. Вместо того, чтобы манипулировать переданным массивом, вы должны управлять порядком индексов, а затем отмечать верхнюю часть N. Это займет линейное время.

Answer 4

Я бы оптимизировал это при необходимости следующим образом. Если это не нужно оптимизировать, то делайте то, что хотите.

1. Если массив меньше N "верхнего N", то отметьте все TRUE. O (N)
2. Пройдите arr пунктов и отметьте все ложные, в то же время сохраняйте список arr позиции и значения из лучших элементов N. Кроме того, вам нужно только проверить/сравнить против N-го элемента, самого низкого, больше (topN [N-1], arr [i]). В то время как верхний N заполняется до N, когда итерация выполняется над arr [0] до arr [N-1] должно быть условие, чтобы просто добавить его в верхний список N до тех пор, пока N не будет заполнено, все еще сохраняя самое низкое значение на дно. O (обр.размер())
3. Теперь, когда все помечены ложная петля над верхним списком N и вернуться назад и знак в обрах позиция, которые так же верно, как они были в верхнем N. O (N)

Таким образом, общая стоимость: O (N + arr.size())

Answer 5

Я предполагаю, что мы говорим о PHP здесь, потому что вопрос помечен PHP. Любой умный алгоритм, который вы попытаетесь реализовать, будет медленнее, чем использование встроенной функции. Это как раз то, как работает PHP, это не хорошо для хрустких чисел в пользовательском пространстве.

Так что вам нужно сделать, это отсортировать копию массива и сохранить ключи из верхних N элементов, затем выполнить итерацию по массиву и пометить указанные элементы. Но есть улов: сортировка PHP нестабильна. Это означает, что если вы хотите использовать позиции элементов в случае связей, вам придется сделать это самостоятельно. Поэтому вместо использования функции, такой как asort() или arsort(), вам нужно будет использовать array_multisort().

Результат таков:

function mark(array $arr, $n, $order = SORT_DESC) 
{ 
    $keys = $values = $position = array(); 

    $i = 0; 
    foreach ($arr as $k => $v) 
    { 
     $keys[]  = $k; 
     $values[] = $v; 
     $position[] = $i; 

     ++$i; 
    } 

    // sort values in given $order, use their position as tiebreaker (always in ascending order) 
    array_multisort($values, $order, $position, SORT_ASC, $keys); 
    $mark = array_flip(array_slice($keys, 0, $n)); 

    $ret = array(); 
    foreach ($arr as $k => $v) 
    { 
     $ret[] = array($v, isset($mark[$k])); 
    } 

    return $ret; 
} 

Который производит

SORT_DESC 
[3,6,6,6,6,6,2] => [[3,false],[6,true],[6,true],[6,true],[6,false],[6,false],[2,false]] 
[3,5,2,6,2]  => [[3,true],[5,true],[2,false],[6,true],[2,false]] 

SORT_ASC 
[3,6,6,6,6,6,2] => [[3,true],[6,true],[6,false],[6,false],[6,false],[6,false],[2,true]] 
[3,5,2,6,2]  => [[3,true],[5,false],[2,true],[6,false],[2,true]]