【算法】无序数组中求中位数

素颜马尾好姑娘i 2022-06-07 01:56 140阅读 0赞

### 问题 ###

> 给定一个int数组A，为传入的数字序列，同时给定序列大小n，请返回一个int数组，代表每次传入后的中位数。保证n小于等于1000

或者

> 求一个无序数组的中位数。 如：\{2,5,4,9,3,6,8,7,1\}的中位数为5。 要求：不能使用排序，时间复杂度O(n)。

### 分析 ###

因为题目指定不能使用排序算法，而且要求时间复杂度O(n)，也就是要求一次遍历就得给出结果。所以排序算法基本上没有用武之地。

寻寻觅觅之后终于找到一种使用大小堆的方式来实现，看着思路很不错。它通过建立两个堆

*  一个**最大堆**，用来存储比较小的那一半组元素，同时堆顶最大（也就是最靠近中位数的那个）。
 *  一个**最小堆**，用来存储比较大的后半组元组，同时堆顶最小（也是最靠近中位数的那个）。

这样只需遍历一遍，将元素分配到对应的堆，那么最后的中位数要么就是最大堆堆顶，要么就是最小堆的堆顶。具体步骤如下：

1.  通过最大堆、最小堆来实现实时中位数的获取。
2.  最大堆中存放比最小堆小的元素。
3.  如果最大堆的堆头元素大于最小堆，则进行交换。
4.  偶数下标的元素存入最小堆，奇数下标的元素存入最大堆。

### 实现 ###

我们借助Java中的PriorityQueue来建立堆，它就是一个完全二叉树实现的优先级队列，构造函数还支持传入Comparator来自定义大小顺序，省去了建堆的额外操作。大家想要深入了解的可以参考这篇文章：[深入理解Java PriorityQueue][Java PriorityQueue]。

/**
     * 1. 通过最大堆、最小堆来实现实时中位数的获取。
     * 2. 最大堆中存放比最小堆小的元素。
     * 3. 如果最大堆的对头元素大于最小堆，则进行交换。
     * 4. 偶数下标的元素存入最小堆，奇数下标的元素存入最大堆。
     * 
     * @param arr
     * @param cmp  比较器
     */
    public static <E> List<E> findMedianFromRandomArray(E[] arr, Comparator cmp){
        
    	List<E> res = new ArrayList<E>(arr.length);
    	PriorityQueue<E> maxHeap = new PriorityQueue<E>(cmp);
    	PriorityQueue<E> minHeap = new PriorityQueue<E>();
    	
    	for(int i = 0; i < arr.length; i++){
        
    		if(i % 2 == 0){
        
    			// 存入最小堆前判断当前元素是否小于最大堆的堆顶元素
    			if(!maxHeap.isEmpty() && cmp.compare(arr[i], maxHeap.peek()) > 0){
        
    				minHeap.offer(maxHeap.poll());
    				maxHeap.offer(arr[i]);
    			}else{
        
    				minHeap.offer(arr[i]);
    			}
    			res.add(minHeap.peek());
    		}else{
        
    			// 存入最大堆前判断当前元素是否大于最小堆的堆顶元素
    			if(!minHeap.isEmpty() && cmp.compare(minHeap.peek(),arr[i]) > 0){
        
    				maxHeap.offer(minHeap.poll());
    				minHeap.offer(arr[i]);
    			}else{
        
    				maxHeap.offer(arr[i]);
    			}
    			res.add(maxHeap.peek());
    		}
    	}
    	return res;
    }

测试代码如下：

public class Median {
        
    	
    	public static void main(String args[]){
        
    		Integer arr[] = new Integer[]{
        2,5,4,9,3,6,8,7,1};
    //		Integer arr[] = new Integer[]{1,2,3,4,5,6};
    		
    		Comparator<Integer> cmpLarger = new Comparator<Integer>() {
        
    			public int compare(Integer arg0, Integer arg1) {
        
    				return arg1 - arg0;
    			}
    		};
    		List<Integer> res = findMedianFromRandomArray(arr, cmpLarger);
    		System.out.println(Arrays.asList(res));
    	}
    }

### 参考资料 ###

*  [无序数组中求中位数][Link 1]
 *  [深入理解Java PriorityQueue][Java PriorityQueue]

[Java PriorityQueue]: http://www.cnblogs.com/CarpenterLee/p/5488070.html
[Link 1]: http://blog.csdn.net/wzy_1988/article/details/72923641