一个排序的数组马克的前N个元素 [英] Mark the top N elements of an unsorted array

问题描述

我有一个排序的数组（生成模辊），我想选择它的前N个元素（这是微不足道的排序和剪断），但同时保持他们为了纪念他们。

I have an unsorted array (of generated die rolls), and I want to select the top N elements of it (which is trivial with sort-and-snip), but mark them while keeping them in order.

例如：

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向上，并且是任何长度的，并显着的元素的量是可变的。

The array may contain any values from 1 up, and be of any length, and the amount of marked elements is variable.

我可以忍受

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

（即，会被标记为错误的号码去无人盯防的），但我宁愿避免它。

(I.e., numbers that'd be marked false to go unmarked), but I'd rather avoid it.

什么是强制的是，数组的顺序保持不变。

What's mandatory is that the order of the array stays unchanged.

如果顶部部分重复出现（如：中[6,6,6,6,6,6]前3名），标志着第3个元素

If the top elements are repeated (eg: top 3 of [6,6,6,6,6,6]), mark the first 3 elements.

（N是足够小的复杂性没有很大关系。）

(N is sufficiently small for complexity not to matter much.)

编辑：奖金点：添加参数顶和底模式之间进行切换

Bonus point: add a parameter to switch between "top" and "bottom" mode.

推荐答案

目前公认的答案扫描输入列表m次。这一次对其进行扫描两次即可。为O（n）与O（N * M）。你需要一个堆数据结构。这是Python编写的。

The currently accepted answer scans the input list m times. This one scans it just twice. O(n) vs O(n*m). You need a heap data structure. Here it is in 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]]

这篇关于一个排序的数组马克的前N个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！