这是一个面试问题.您需要设计一个包含整数值的堆栈,以便getMinimum()函数返回堆栈中的最小元素.
例如:考虑下面的例子
case #1 5 --> TOP 1 4 6 2 When getMinimum() is called it should return 1, which is the minimum element in the stack. case #2 stack.pop() stack.pop() Note: Both 5 and 1 are poped out of the stack. So after this, the stack looks like, 4 --> TOP 6 2 When getMinimum() is called is should return 2 which is the minimum in the stack.
制约性:
我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.
我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).
有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？
我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().
感谢所有的建议.
我感兴趣的是创建一个类似于堆栈的Java数据结构,它尽可能高效地支持以下操作:
这个数据结构最快的实现是什么？我怎么能用Java编写它？
我最近一直在考虑在排序算法中使用面向对象的设计.然而,我无法找到一种合适的方法来进一步制作这种在O(n)时间内进行排序的排序算法.
好的,这是我一周以来的想法.我有一组输入数据.我将为每个输入数据分配一个质量(假设输入数据的类型Mass和类型Sphere.如果我们假设所有对象都是完美的球形物体,其形状与其质量成比例,则最重的物体首先接触地面.).我将把所有输入数据放在距离地球相同距离的空间中.我会让他们自由落体.根据引力定律,最重的一个首先击中地面.它们命中的顺序将为我提供排序数据.这在某种程度上很有趣,但在下面我觉得应该可以使用我迄今为止学到的OO
真的有可能制作一种使用引力拉动场景的分类技术,还是我愚蠢/疯狂？
编辑:同时关闭所有撞击地面的物体,因此我引入了球形物体概念.
我在接受采访时被问到以下问题:如果你有一个整数堆栈,你如何在不使用Collections.max的情况下找到堆栈的最大值,而不是迭代堆栈并比较元素.我用下面的代码回答它,因为我不知道使用任何Collections API或迭代Stack并使用比较的另一种方式.有任何想法吗？
import java.util.Collections;
import java.util.Stack;
public class StackDemo {
public static void main(String[] args){
Stack lifo = new Stack();
lifo.push(new Integer(4));
lifo.push(new Integer(1));
lifo.push(new Integer(150));
lifo.push(new Integer(40));
lifo.push(new Integer(0));
lifo.push(new Integer(60));
lifo.push(new Integer(47));
lifo.push(new Integer(104));
if(!lifo.isEmpty()){
Object max = Collections.max(lifo);
System.out.println("max=" + max.toString());
}
}
}
假设您有许多(键,值)对象要跟踪,包括许多插入和删除.
您需要满足3个要求:
有没有可以做到这一点的数据结构？
我的想法:
优先级队列可以在恒定时间内获得最大值,但我无法查找值.二进制搜索树(2-3树)可以在对数时间内查找,但max也需要O(lgN).如果我试图跟踪BST中的最大值,当我必须删除最大值并找到第二个最大值时需要O(lgN).
我看到了关于在 O(1) 时间内使用 findmin 设计堆栈的问题的答案：
如果请求相同怎么办：
Devise a stack-like data structure that does push, pop and min (or max) operations
in O(1) time. There are no space constraints.
但deletemin也应该是O(1)？是否可以？