我感兴趣的是创建一个类似于堆栈的Java数据结构,它尽可能高效地支持以下操作:
这个数据结构最快的实现是什么？我怎么能用Java编写它？
支持Enque,Dequeue,Peak,Min和Max操作的队列的正确数据结构是什么,并在O(1)时间内执行所有这些操作.
最明显的数据结构是链表,但Min,Max操作将是O(n).Priority Queue是另一个完美的选择,但Enqueue,Dequeue应该以Queue的正常方式工作.(FIFO)
想到的另一个选项是Heap,但是我无法弄清楚如何使用Heaps设置具有Min,Max操作的队列.
任何帮助深表感谢.
我几天前采访了亚马逊.我无法回答其中一个让我满意的问题.我在采访后试图得到答案,但到目前为止我还没有成功.这是一个问题:
你有一个大小为n的整数数组.给你参数k在哪里k < n.对于k阵列中每个连续元素大小的每个段,您需要计算最大值.您只需返回这些最大值的最小值.
例如给出1 2 3 1 1 2 1 1 1,k = 3答案是1.
该段将是1 2 3,2 3 1,3 1 1,1 1 2,1 2 1,2 1 1,1 1 1.
每个段中的最大的值是3,3,3,2,2,2,1.因此,答案是
这些值中的最小值.11
我想出的最佳答案是复杂度O(n log k).我所做的是创建一个带有第一个k元素的二叉搜索树,获取树中的最大值并将其保存在变量中minOfMax …
可能重复:
为什么要使用两个堆栈来建立队列？
我得到了这个赋值问题,要求我使用两个堆栈实现一个队列.我的问题不是如何做到,而是为什么这样做？我不是来自计算机背景,我试图找到答案,但无法真正找到原因吗？我认为你的专家可以帮助我理解实现这样一个东西有什么好处.我发现了一篇相关文章为什么要使用两个堆栈来建立队列？谈论这个,但想知道是否还有更多.
我有一个(大)数值数据(大小)数组,N并希望计算一个具有固定窗口大小的运行最大值的数组w.
更直接的是,我可以out[k-w+1] = max{data[k-w+1,...,k]}为k >= w-1(定义基于0的数组,如在C++中)定义一个新数组.
有没有更好的方法来做到这一点N log(w)？
[我希望在N没有依赖的情况下应该有一个线性的w,比如移动平均线,但找不到它.对于N log(w)我认为有一个排序的数据结构,它会做管理的方式insert(),delete()并extract_max()完全在log(w)以下大小的结构w-就像一个排序二叉树,例如.
非常感谢你.
我有Ñ的不同长度的字符串小号1,S 2,...,S Ñ我要显示在终端上Ç列.终端的宽度为m个字符.每列i具有一定宽度w i,其等于该列中最长条目的宽度.每对列之间有空间的一定量的小号.包括空间之间的所有列的总宽度不能大于端子的宽度(w 1 + w 2 + ... + w c +(c-1)·s≤m).每列应包含⌈n / c⌉字符串,除非n不能由c均匀分割,在这种情况下,最后几列应缩短一个条目,或者只有最后一列应短,取决于字符串是否排列横向或向下.
是否存在有效的(例如O(n·w),其中w = max(w 1,w 2,...,w n))算法,以计算出我可以适应c列的最大列数,如果......
字符串排列整齐
string1 string2 string3 string4
string5 string6 string7 string8
string9 string10
弦向下排列
string1 string4 string7 string10
string2 string5 string8
string3 …我们给出了一个由n个元素和一个整数k组成的数组.假设我们想在数组中滑动长度为k的窗口,报告每个窗口中包含的最大值.例如,给定数组
15 10 9 16 20 14 13
给定长度为4的窗口,我们将输出
[15 10 9 16] 20 14 13 ---> Output 16
15 [10 9 16 20] 14 13 ---> Output 20
15 10 [ 9 16 20 14] 13 ---> Output 20
15 10 9 [16 20 14 13] ---> Output 20
结果就是这样
16 20 20 20
我通过跟踪每个点上窗口的最大元素来解决问题,但是当最大元素滑出窗口时遇到了问题.那时,我想不出一个快速的方法来弄清楚剩下的最大元素是什么.
有谁知道解决这个问题的有效算法？
如何在0(1)时间复杂度的任何时间从队列中检索max和min元素？之前我使用Collections.max和min来查找元素,但这将是0(n).
我想有效地计算滚动的最大值和最小值.比每次窗口移动时重新计算所有使用值中的最大值/最小值更好.
这里有一篇帖子提出同样的问题,有人发布了一个涉及某种堆栈方法的解决方案,据说根据其评级工作.但是,对于我的生活,我再也找不到它.
在寻找解决方案或帖子时,我们将不胜感激.谢谢你们!