algorithm - 在 O(1) 时间内找到数组中的 k 个最大元素

Question

push()通过使用辅助数据结构创建堆栈类来跟踪每个和中的 k 最大/最小，是否有可能具有 O(1) 时间复杂度来找到数组中的 k 个最大或最小数字pop()。由于检索是 O(1)，因此在 get 方法中返回 k 个元素

标签： algorithmdata-structuresstack

Answer 1

是的，只有当您的数组按排序顺序时，才能通过 O(1) 复杂度找出第 K 个最大元素或最小元素。