我正在寻求设计支持以下算法的帮助:
initiation(M) Given Set of M unique natural number initialize the data structure in O(f(n)) f is some polynomial function lookUP(x) given a natural number find if x in S in O(1). find Kth(k) return the kth largest number in S in O(1).
当我尝试使用哈希来支持 O(1) 操作时，这个问题对我来说似乎很简单，但后来我想起哈希表不支持元素之间的比较，我知道我可以在 O(n^ 2) 我完成了。
对于 f(n) 是否有更快的解决方案作为多项式 O(f(n)) init？
最佳答案
I know i can sort the array in O(n^2) and i finish.
排序可以在 O(nlogn) 中更快地完成，其中 n 是问题的大小。这种算法的一个例子是 Quicksort .
数据结构可以是一个数组，您可以在其中以 O(nlogn) 的成本对其进行排序。然后你可以在 O(1) 时间内为最大的第 k 个元素建立索引。
但是，为了搜索任何 x，您将不得不使用二分查找，其成本为 O(logn)。
但是您的元素是独一无二的。因此，您可以使用索引数组，例如，如果您的输入是 [1, 2, 3, 5]，那么您的 bool 索引数组将是 [1, 1, 1, 0, 1]，其中 0 表示该索引中的数字不存在于您的输入中。这样您就可以在 O(1) 时间内查找每个 x。
但是现在找到最大的第k个元素需要到第k个索引，检查那个槽，如果它是空的，然后检查下一个槽，直到找到一个1，这意味着这个槽的编号存在于我们的输入中。这将花费 O(m)，其中 m 是到达第 k 个索引后您将遇到的空槽数，平均而言，它应该很小，并且可以假设为常数，产生 O 的时间复杂度(1).
关于arrays - 设计一个使用散列并支持比较的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44409836/