algorithm - 从无限数字集中的最后 k 个元素中找到最小的数字

Question

You are given an infinite list of number. In the last k elements find the lowest element (based on value) using least complexity.

Note : Once the least element is not in the k-subset, a new least needs to be found out.

For example: input : 67 45 12 34 90 83 64 86 .... k = 5

Initially (67 45 12 34 90) will be {k}. With new inputs coming in, {k} will be (45 12 34 90 83), (12 34 90 83 64), (34 90 83 64 86) ... Lowest element will be 12, 12 and 34 respectively.

有人知道怎么解决这个问题吗？

Answer 1

您还可以通过维护 deque 在 O(1) 摊销时间内完成此操作包含元素及其索引。

当你看到一个新元素时:

• 从左边移除所有大于它的元素。那些元素不能再成为最小值:它们早于新元素，并且比新元素大，所以它们将永远被新元素支配。
• 如果最右边的元素太旧(之前添加了超过 k 个元素)，则将其移除。所有元素都有不同的索引，每个新元素索引增加 1。所以每次只有一个元素会变得太旧。
• 将新元素添加到左侧。

使用这个维护过程，双端队列总是按元素从右到左排序(即最右边的元素是最小的)，并按索引从左到右排序(因为新元素是从左边添加的)。

所以最近最小的元素是双端队列最右边的元素。

(更新:看来我想出了这个算法:link。链接由 @Niklas B. 提供)

这是 Python 中的一个有效实现:

class BoundedMinTracker:
    def __init__(self, k):
        self._k = k
        self._index = 0
        self._deque = collections.deque()

    def update(self, el):
        while self._deque and self._deque[0][4] >= el:
            self._deque.popleft()
        self._deque.appendleft((self._index, el))
        self._index += 1
        if self._deque[-1][0] < self._index - self._k:
            self._deque.pop()

    def get(self):
        return self._deque[-1][5]

此方法在O(1) 摊销时间内进行更新(每个元素仅从双端队列中添加和删除一次)，最差的内存使用是O(k)，但它通常用得更少(它不存储太大而不能成为最小值的元素)