java - 数字流和查找第 n/2 个元素的最佳空间复杂度

Question

我试图解决这个问题，其中将给出长度不超过 M 的数字流。您不知道流的确切长度，但可以确定它不会超过 M。在流的末尾，考虑到 N 元素出现在流中，您必须告诉流的第 N/2 元素。解决这个问题的最佳空间复杂度是多少

我的解决方案:我想我们可以取一个大小为 m/2 的队列，然后压入两个元素，然后弹出 1 个元素并继续直到流结束了。 n/2th 将排在队首。任何方式的时间复杂度都将是最小 O(n)，但对于这种方法，空间复杂度是 m/2 ..有没有更好的解决方案？

Answer 1

我希望很明显，您至少需要 N/2 内存分配(除非您可以重新迭代您的 steam，再次读取相同的数据)。您的算法使用 M/2，考虑到 N 上限为 M 的事实会让您看起来并不重要将选择，因为 N 可以上升到 M。

但它不需要。如果您认为 N 比 M 小(例如 N=5 和 M=1 000 000) 那么你会浪费很多资源。

我会推荐一些动态增长的数组结构，比如 ArrayList，但这不利于删除第一个元素。

结论:时间和内存复杂度都可以达到O(N)，而且再好不过了。

关于 ArrayList 的友好编辑:将元素添加到 ArrayList 是在“摊销常数时间”中进行的，因此添加 N 项的时间复杂度为 O(N)。然而，删除它们是线性的(根据 JavaDoc)，因此您绝对可以在时间和空间上获得 O(N)，但仅当您不删除任何内容时。如果你确实删除了，你在空间上得到 O(N) (O(N/2) = O(N))，但你的时间复杂度会增加。