import java.util.ArrayDeque;
import java.util.Iterator;
public class ArrayDequeDemo {
public static void main(String[] args) {
ArrayDeque<Integer> que = new ArrayDeque<Integer>();
// add elements in queue
que.add(2);
que.add(1);
que.add(2);
que.add(2);
que.add(6);
que.add(4);
que.add(2);
que.add(5);
Integer median = peekMedian(que);
System.out.println(median);
}
private static Integer peekMedian(ArrayDeque<Integer> que){
Integer ele=0; //required number
int size=que.size();
//finding the index of ele.
int elementFromlastIndex= (size/2)+1;
Iterator descItr = que.descendingIterator();
int counter=0;
// iterate in reverse order till the index of ele is not reached.The loop will break when when index of ele is reached and thereby finding required element.
while(descItr.hasNext() && counter!=elementFromlastIndex) {
ele =( Integer)descItr.next();
++counter;
if(counter==elementFromlastIndex)
break;
}//while
return ele;
}
}
}//class
3条答案
按热度按时间vxqlmq5t1#
我想我知道怎么做了,我昨天被要求执行。
在o(1)时间内实现max或min很容易,不是吗?为什么不把队列分成两个队列,一个存储比中间值小的项目,一个存储比中间值大的项目,始终保持这种关系,当你插入项目时,依次插入到每个队列中,你就可以得到中间值。
保持这个关系可能会有一些操作,但我认为完全是o(1)时间,因为我们在o(1)中得到最大值或最小值,而inset可以在o(1)中下降,所以它仍然是o(1),听起来不错。
我希望我是对的。如果有什么不对劲,请告诉我。
cngwdvgl2#
这看起来像是一个家庭作业,所以我将发布一个算法来解决这个问题:
创建一个新队列,作为对象的辅助集合来帮助您。
开始将对象从初始队列中取出,然后在辅助队列中对它们进行排队。
如果知道队列的原始大小,当到达(size/2+1)第n个元素时,请使用辅助对象保留其值的副本。
继续执行步骤2中的过程。
如果可以,用辅助队列替换您的队列,否则重复过程2中从辅助队列到原始队列的过程。
返回带有中值的辅助对象。
顺便说一下,我想你对中值有不同的概念。或者问题就是这样被提出的。
注意:如果您的任务是在不删除队列中的任何对象的情况下执行此操作,那么这是不可能的,至少您可以将队列作为数组或链接列表进行威胁并对其进行迭代。
我将向您展示一个使用java队列的代码实现。
lvmkulzt3#
试试这个