首页 > 试题广场 >

实时中位数

[编程题]实时中位数

热度指数：5421 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int数组A，初始为空，现生成n个随机数依次传入数组中，将返回一个int数组，数组中的每个元素代表每次传入随机数到数组A后A中全部数的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字，n为已传入数字个数)保证n小于等于1000。

测试样例：

[1,2,3,4,5,6],6

返回：[1,1,2,2,3,3]

算法知识视频讲解

Java

已注销

import java.util.*;


public class Middle {
    public int[] getMiddle(int[] A, int n) {
        // write code here
        int res[] = new int[n];
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((u, v) -> v.compareTo(u));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            maxHeap.offer(A[i]);
            minHeap.offer(maxHeap.poll());
            if (maxHeap.size() < minHeap.size()) {
                maxHeap.offer(minHeap.poll());
            }

            res[i] = maxHeap.peek();
        }

        return res;
    }
}

编辑于 2024-03-01 15:33:35 回复(0)

Java

拙剑无式

import java.util.*;

public class Middle {
    public int[] getMiddle(int[] A, int n) {
        int[] res = new int[n];
        PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2) -> o2 - o1);
        PriorityQueue<Integer> min = new PriorityQueue<>();
        max.add(A[0]);
        res[0] = A[0];
        for (int i = 1; i < n; i++) {
            if (A[i] <= res[i - 1]) {
                max.add(A[i]);
            } else
                min.add(A[i]);
            if (min.size() > max.size()) {
                max.add(min.poll());
            }
            if (max.size() - 1 > min.size()) {
                min.add(max.poll());
            }
            res[i] = max.peek();
        }
        return res;
    }
}

发表于 2020-04-24 20:53:13 回复(0)

Java

Holiday_12138

import java.util.*;

public class Middle {
    public int[] getMiddle(int[] A, int n) {
        int[] res = new int[n];
        PriorityQueue<Integer> maxHeap = new PriorityQueue(n,new Comparator<Integer>(){
            public int compare(Integer i1,Integer i2){
                return i2.compareTo(i1);
            }
        });
        PriorityQueue<Integer> minHeap = new PriorityQueue(n);
        for(int i=0;i<n;i++){
            if(maxHeap.isEmpty()||A[i]<=maxHeap.peek())
                maxHeap.add(A[i]);
            else
                minHeap.add(A[i]);
            if(minHeap.size()>maxHeap.size())
                maxHeap.add(minHeap.poll());
            if(minHeap.size()+1<maxHeap.si敏感词Heap.add(maxHeap.poll());
            res[i]=maxHeap.peek();
        }
        return res;
    }
}

发表于 2017-05-04 17:16:40 回复(1)

Java

蓝胖子SHD

//插入排序
import java.util.*;
public class Middle {
    public int[] getMiddle(int[] A, int n) {
        // write code here
         int[]res=new int[A.length];
		 res[0]=A[0];
		 for (int i = 1; i < A.length; i++) {
			int k=i-1;
			int tem=A[i];
			while(k>=0&&A[k]>tem){
				A[k+1]=A[k];
				k--;
			}
			A[++k]=tem;
			res[i]=A[i/2];
		}
		 return res;
    }
}

发表于 2016-08-13 15:52:24 回复(0)