阅读 479

算法:求一个源源不断到来数据中的中值元素?

问题描述:

在上一个问题(www.zifangsky.cn/1550.html)中我们已经计算了“前K个最大元素”和“前K个最小元素”。其实这个问题还有一个变种,那就是如何求这个队列的中值元素。

算法实现:

中值就是排序后中间那个元素的值(PS:假如元素个数为奇数,没有歧义,取中间那个元素;假如元素个数为偶数,为了算法实现简单,这里我们约定中间那两个元素任取一个都可以)。

如果元素个数是确定的,显然我们可以通过排序后取中间那个值即可。如果元素源源不断到来,那么如何实时返回当前已经输入进来的这些元素的中值元素呢?

上一个题目,我们通过这种数据结构实现的优先队列得以解决,这个问题我们同样可以通过优先队列求解。具体实现思路如下:

  1. 定义一个最大堆和最小堆,假设当前中值元素是 median,那么我们在最大堆中维护小于 median 的元素,在最小堆中维护大于 median 的元素;
  2. 每当一个新元素到达时,首先跟 median 比较,如果等于 median,则抛弃不做处理,否则根据上述规则将之添加到最大堆/最小堆;
  3. 执行完步骤2之后,如果两个堆的个数差大于等于2,则需要对整个存储结构进行调整。调整方式如下:
    1. 将中值元素 median 添加到元素较少那个堆;
    2. 然后将元素较多那个堆的根节点移出作为新的中值元素 median。

当然,如果你觉得像上面这样的文字描述不太好理解,那么下面我们通过一个简单的数组{3, 4, 5, 1, 2}来具体分析一下。

通过堆求中值元素

通过堆求中值元素

理解了算法的实现思路后,使用代码来实现那就很简单了。下面我给出一份我写的示例代码,以供大家参考:

import cn.zifangsky.queue.PriorityQueue;
import org.junit.Test;

import java.util.Arrays;
import java.util.Collection;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * 求很大一个的乱序序列的中位元素?
 *
 * @author zifangsky
 * @date 2020/5/15
 * @since 1.0.0
 */
public class Problem_002_Median {
    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        //1. 生成 1~100 的整数
        Integer[] arr = IntStream.rangeClosed(1, 100).boxed().toArray(Integer[]::new);

        //2. 将数组的顺序打乱
        shuffle(arr);

        //3. 求中位元素
        Solution<Integer> solution = new Solution<>();
        solution.addAll(Arrays.asList(arr));
        System.out.println("数组中的中位元素是:" + solution.getMedian());
    }


    static class Solution<T extends Comparable<? super T>> {
        /**
         * 优先队列(最大堆)
         */
        private PriorityQueue<T> maxQueue;

        /**
         * 优先队列(最小堆)
         */
        private PriorityQueue<T> minQueue;

        /**
         * 当前中位数
         */
        private T median;

        public Solution() {
            this.maxQueue = new PriorityQueue<T>(PriorityQueue.Mode.MAX);
            this.minQueue = new PriorityQueue<T>(PriorityQueue.Mode.MIN);
        }

        /**
         * 添加一个集合进来
         */
        public void addAll(Collection<? extends T> c){
            for(T e : c){
                this.add(e);
            }
        }

        /**
         * 往队列中添加新值
         */
        public void add(T data){
            if(data == null){
                return;
            }

            //1. 如果当前中位数没值,则直接复制给中位数
            if(this.median == null){
                this.median = data;
                return;
            }

            //2. 如果新值等于中位数,则不作处理
            if(data.compareTo(this.median) == 0){
                return;
            }

            //3. 如果新值大于中位数,则放入最小堆,相反放入最大堆
            if(data.compareTo(this.median) > 0){
                this.minQueue.push(data);
            }else{
                this.maxQueue.push(data);
            }

            //4. 如果两个堆的数目相差超过2,则需要重新平衡两个堆
            if(this.maxQueue.size() - this.minQueue.size() >= 2){
                //4.1 将中位数插入到最小堆
                this.minQueue.push(this.median);
                //4.2 将最大堆出队并设置为新的中位数
                this.median = this.maxQueue.pop();
            }else if(this.minQueue.size() - this.maxQueue.size() >= 2){
                //4.1 将中位数插入到最大堆
                this.maxQueue.push(this.median);
                //4.2 将最小堆出队并设置为新的中位数
                this.median = this.minQueue.pop();
            }
        }

        /**
         * 返回中位元素
         */
        public T getMedian(){
            return this.median;
        }
    }

    /**
     * 洗牌
     */
    private void shuffle(Integer[] arr){
        if(arr == null || arr.length < 1){
            return;
        }
        Random rnd = new Random();

        for(int i = (arr.length -1); i > 0; i--){
            swap(arr, i, rnd.nextInt(i));
        }
    }

    private void swap(Integer[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
复制代码

示例代码输出如下:

数组中的中位元素是:51
复制代码

需要注意的是,上面的示例代码使用了我自己实现的优先队列(PS:优先队列的本质就是最大堆/最小堆),如需参考该类的实现可以看我的这个项目:gitee.com/zifangsky/D…。当然,大家也可以直接使用JDK中的优先队列(java.util.PriorityQueue)。