java - 在 JAVA 的 FIFO 队列中计算 PeekMedian()

Question

尽快需要帮助。我想实现一个 peekMedian 函数，它查看所有对象中具有中值的对象，而不将其从队列中删除。它应该返回值为(size/2 + 1) th最低的对象。

例如。假设一个队列具有以下值。{ 2, 1, 2, 2, 6, 4, 2, 5} 那么该方法应该返回 2 并且不会删除该对象。

我曾尝试使用collection.sort()但不应根据问题对队列进行排序。我还尝试复制数组中的队列元素并找到第 n 个最小值并返回该值。但问题是“返回对象”。..而且解决方案的复杂性应该更低。

Answer 1

尝试这个

        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

Answer 2

我想我知道该怎么做了，昨天我被要求执行。

在 O(1) 时间内实现最大值或最小值很容易，不是吗？为什么不将队列分成两个队列，一个存储小于中位数的项目，一个存储大于中位数的项目，始终保持这种关系，并且当您插入项目时，依次插入到每个队列中，您可以获得中位数。

保持关系时可能会有一些操作，但我认为这将是 O(1) 时间，因为我们在 O(1) 中得到最大值或最小值，并且 inset 可以在 O(1) 中下降，所以它仍然是 O(1) ， 听起来不错。

我希望我是对的。如果有什么问题，请告诉我。

Answer 3

这看起来像一个家庭作业，所以我会发布一个算法来解决这个问题：

1. 创建一个新队列，它将帮助您作为对象的辅助集合。
2. 开始从初始队列中将对象出列并在辅助队列中排队。
3. 如果您知道队列的原始大小，那么当您到达第(size/2 + 1)n 个元素时，使用辅助对象来保留其值的副本。
4. 继续步骤 2 中的过程。
5. 如果可以的话，用你的辅助队列替换你的队列，否则从辅助队列到原始队列重复第 2 步中的过程。
6. 返回具有中值的辅助对象。

顺便说一句，我认为您对中位数有不同的概念。或者也许这就是问题的提出方式。

注意：如果您的任务是在不删除队列中的任何对象的情况下执行此操作，那么这是不可能的，至少您将队列威胁为 Array 或 LinkedList 并对其进行迭代。

---

我将向您展示使用 Java Queue 的代码实现。

public <T> T peekMedian(Queue<T> queue) {
    int medianIndex = queue.size() / 2 + 1; //based on your question.
    Queue<T> auxQueue = new LinkedList<T>();
    T result;
    int count = 1;
    while(queue.peek() != null) {
        auxQueue.add(queue.pop());
        if (count == medianIndex) {
            result = auxQueue.peek();
        }
        count++;
    }
    while(auxQueue.peek() != null) {
        queue.add(auxQueue.pop());
    }
    return result;
}