在O（1）时间复杂度的堆栈中查找最小值 [英] Finding minimum value in a stack with O(1) time complexity

问题描述

如何在O（1）复杂度的堆栈中找到最小值。为了找到堆栈的最小值，我找到了两种方法：

1）min =堆栈的最高值

遍历堆栈并更新最小值以获得堆栈的最小值。

这需要O（N）复杂度，其中N是堆栈中元素的数量



2）将堆栈元素放在minheap中

将提取的根值将是堆栈中的最小值

这需要O（N log（N））



但是如何实现O（1）算法，一种独立于输入大小的算法。



这里的假设是堆栈已经加载了元素



另一个问题是数据结构在C或java中是否有效？因为在C中我们手动使用指针来分配内存.Java具有内置实现，以及实现它们的引用对象？哪一个要用？

解决方案

虽然需要更多的内存和慢速插入一点，但我很想保持一个变量，保持一个指向项目的指针最低/最高价值。只需检查每个新添加。如果它小于/大于当前维持的最小值或最大值，请将指针设置为新添加的项目。类似于某些（非cricular）链表实现维护指向列表中尾部项的指针的方式。如果这是一个更快的解决方案总体上取决于你的应用程序需要访问这些数据的方式。



添加一百万个项目但从不检查最小值使用这种方法会比你想要分钟时只是通过列表一样慢。即1,000,000比较vs 0.



添加一百万个项目然后使用min，然后再添加一百万个项目到同一个列表再次查找min将更快用这种方法。

即1,000,000 + 1,000,000 = 2,000,000与1,000,000 + 2,000,000的天真方法。









至于C与Java中数据结构的效率 - 这不是一场竞赛。一个是一个简单的做你喜欢的情况，另一个是我们管理的记忆 - 所以你不必接近。可以用每个编写非常好的软件。同样可以用任何一种语言写出可憎的东西。一个称职的程序员可以使用C创建一个更好，更快的实现。



如果使用Java，同一个程序员将​​有更多时间与朋友和家人共度。

当实施对于手头的任务足够快时，许多人选择朋友+家人而非工作室隔间和'完美代码'。



因此，除了您喜欢的花时间之外，哪一个取决于应用程序的目的及其所需的性能。如果你试图在汇编中编写MS Office，那你就疯了。同样，如果您尝试编写Grand Theft Auto或Gran Turismo或< insert_name_of_high-performance_game_here>在Java中，你的理智将被检查！

How to find the minimum value in a stack with O(1) complexity.To find minimum value of a stack I found two ways :
1) min = top value of the stack
Traverse the stack and update the min value to get the minimum value of the stack.
This requires O(N) complexity where N is the number of elements in the stack

2) Put the stack elements in a minheap
The root value that will be extracted will be the minimum value in the stack
This requires O(N log(N))

But how do I implement O(1) algorithm , an Algorithm that is Independent of the Input size.

Here the assumption is that the stack is already loaded with elements

Another question is that data structures is efficient in C or java?Because in C we manually use pointers to allocate memory.Java has in-build implementation , as well as reference objects to implement them?Which one to go for?

解决方案

While it would take a little more memory and slow-down inserts a little, I'd be tempted to maintain a variable the held a pointer to the item with the lowest/highest value. Simply check each new addition. If it's smaller/larger than the currently maintained min or max, set the pointer to the newly added item. Similar to the way that some (non-cricular) linked list implementations maintain a pointer to the tail item in the list. If and by how much this is a faster solution overall depends entirely on the way your application needs to access this data.

Adding a million items but never checking for the min will be slower with this method than it would be if you just stepped through the list when you wanted the min. I.e 1,000,000 comparisons vs 0.

Adding a million items then using the min, followed by adding another million items to the same list and again looking for the min will be quicker with this method.
I.e 1,000,000 + 1,000,000 = 2,000,000 versus 1,000,000 + 2,000,000 for the naive approach.




As for efficiency of data structures in C vs Java - it's no contest. One is a bare-bones-do-what-you-like situation, the other is a we'll-manage-memory-so-you-dont-have-to approach. It's possible to write very good software with each. It's equally possible to write abominations with either language. A competent programmer can create a 'better', faster implementation with C.

The same programmer will have more time to spend with friends and family if they use Java.
When the implementation is fast enough for the task at hand, many people choose friends + family over workstation cubicles and 'the perfect code'.

So, which one to go for depends on the purpose of the application and its required performance - in addition to your preferred way of spending time. If you tried to write MS Office in assembly you're nuts. Likewise, if you tried to write Grand Theft Auto or Gran Turismo or <insert_name_of_high-performance_game_here> in Java, your sanity would be examined!

这篇关于在O（1）时间复杂度的堆栈中查找最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！