首页 > 试题广场 >

请设计一个整数容器,支持两个操作:add(x)和p...

[问答题]

  请设计一个整数容器,支持两个操作:add(x)popMedia()两个操作。add(x)是向容器中加入一个整数;popMedia()是返回容器中当前所有数的中位数,如果中位数是容器中的数字,则返回的同时还从容器中把它删除。无需写出完全代码,描述清楚设计实现即可。另外,你能使两个操作都小于O(N)的时间吗?

注:中位数定义为:如果容器中整数的数量为奇数个,则是最中间的那个数字,如果为偶数个,则是最中间两个数的平均值。

令L的中位数为m,用一个大顶堆存储数列L中不大于m的元素(即L按从小到大排列时的前半部分),用一个小顶堆存储数列L中不小于m的元素(即L按从小到大排列时的后半部分),其中这两个大小顶堆均不包含中位数m。每次往数列L插入新元素x时,若x<m,则将其插入大顶堆,否则插入小顶堆。若插入新元素后导致m不再是中位数(即两个堆的元素数目相差2个或2个以上),则将当前的中位数m插入到元素数量较少的那个堆中,然后令元素数量较多的那个堆的堆顶元素为新的中位数,并从该堆顶元素从堆中删除。
发表于 2018-03-23 15:33:57 回复(0)
import java.util.Scanner;
import java.util.Comparator;
import java.util.PriorityQueue;
public class google3 {
    public static void main(String[] args)
    {
       Scanner sc=new Scanner(System.in);
       while(sc.hasNext())
       {
           String s=sc.nextLine();
           String st[]=s.split(" ");
           int []nums=new int[st.length];
           for(int i=0;i<st.length;i++)
               nums[i]=Integer.parseInt(st[i]);
           
           Solution sl=new Solution();
           for(int i:nums)
               sl.add(i);
           System.out.println(sl.popMedia());
       }
    }
}
class Solution
{
    private int count=0;
    //生成一个小顶堆
    private PriorityQueue<Integer> minStack=new PriorityQueue<Integer>();
    //生成一个大顶堆
    private PriorityQueue<Integer> maxStack=new PriorityQueue<Integer>(10,new Comparator<Integer>()
            {
                public int compare(Integer i,Integer j)
                {
                    return j-i;
                }
            });
    
    public void add(int num)
    {
        //如果是偶数个,进入小顶堆
       if(count%2==0)
       {
           maxStack.add(num);
           minStack.add(maxStack.poll());
       }
       else
       {
           minStack.add(num);
           maxStack.add(minStack.poll());
       }
       count++;
    }
    public double popMedia()
    {
        if(count%2==0) return (double)(minStack.poll()+maxStack.poll())/2;
        else return minStack.poll();
    }
}
发表于 2018-01-06 21:56:19 回复(0)