数据流中的中位数

40次阅读

共计 8894 个字符，预计需要花费 23 分钟才能阅读完成。

[TOC]

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用 Insert()方法读取数据流，使用 GetMedian()方法获取当前读取数据的中位数。

public class Solution {public void Insert(Integer num) { }
 
    public Double GetMedian() {}
 
 
}

思路一：使用 partition 函数找出无序数组的中位数

从数据流中读出数据，首先需要一个容器来保存，如果采用数组作为容器，并且保存的时候直接放在数组末尾，不排序，读完之后，再通过 partition 函数从一个无序数组中寻找第 n / 2 大的数（即中位数），这里就可以借鉴“数组中出现次数超过一半的数字”那道题了

import java.util.ArrayList;
import static java.util.Collections.swap;
public class Solution {ArrayList<Integer> list = new ArrayList<>();
    public void Insert(Integer num) {list.add(num);
    }
 
 
    public int partition(ArrayList<Integer> list,int low,int high){int base = list.get(high);
        int i = low - 1;
        // 注意这里 for 循环 j 的起始位置为 low
        for(int j = low; j < high; j++){if(list.get(j) <= base){
                i++;
                swap(list,i,j);
            }
        }
        swap(list,i+1,high);
        return i+1;
    }
 
    public Double GetMedian() {
        double result = 0;
        int index = partition(list, 0, list.size()-1);
        int middle = 0;
        if((list.size() % 2) == 0) {middle = list.size() >> 1;
        }else {middle = (int) Math.floor(list.size() >> 1);
        }
        while (index != middle){if(index > middle){index = partition(list, 0, index - 1);
            }else {index = partition(list, index + 1, list.size()-1);
            }
        }
        if(list.size() % 2 == 0 && index != 0 ){result = (list.get(index) + list.get(index - 1)) / 2.0;
        }else {result = list.get(index);
        }
        return result;
 
    }
 
 
}

思路二：有序的插入到数组

在向数组中插入新的数据时让数组保持有序（可以采用插入排序）每插入一个数，可能需要移动 o(n)个数，对于插入 n 个数，时间复杂度为 o(n^2)

然后在排好序的数组中找出中位数，时间复杂度为 o(1)

思路三：有序的插入到链表

用链表作为保存数据流中的数据的容器，同样的，每插入一个数，需要 o(n)的时间复杂度才能找到合适的插入位置，使用链表和使用数组的时间复杂度一样

思路四：使用平衡二叉树 AVL 树保存数据

插入到 AVL 树中的时间复杂度为 o(logn)，获得中位数的时间复杂度为 o(1)

思路五：使用最大堆和最小堆分别求出两部分的最大值和最小值

具体思路

在堆中插入一个数据的时间效率为 o(logn)，得到堆顶的数据的时间复杂度为 o(1)

  • 数据平均分配到两个堆中，两个堆中的数目只差不超过 1
  • 保证最大堆的数据都小于最小堆的数据

依次将数据流中的数据依次放入最大堆和最小堆，当将要放入最小堆的数据小于最大堆的某些数，那么先将这个数插入最大堆中，然后取出最大堆中的最大值放入最小堆中。同理，如果将要放入最大堆的数据大于最小堆的某些数，那么就先将这个数放入最小堆中，然后取出最小堆的最小值放入最大堆

回顾堆的性质

在使用堆之前我们先来回顾一下堆的性质

1、什么是堆：堆其实就是一颗完全二叉树，除了最底层，其他层的节点都被元素填满，并且最底层尽可能从左到右填入

2、堆有哪些性质：堆一般用一维数组实现，并且该一维数组是堆的层次遍历对应的序列

1）堆的子节点和父节点之间的位置关系：对于节点 i, 它的的左右子节点在一维数组中的索引为：2i+ 1 和 2i+2

它的父节点的索引为 floor((i-1)/2)

2)堆的深度：同二叉树的深度一样为 θ（logn）

3)堆的叶节点的下标分别为：floor(n/2)，floor(n/2)+1,floor(n/2)+2,floor(n/2)+3,floor(n/2)+4…… n-1

接下来就是回顾堆排序了，堆排序是在简单选择排序的基础上演化而来的

回顾简单选择排序

所以我们先回顾一下简单选择排序

  • 简单选择排序的思想：每次从剩下的数中挑选一个最小的数放在已经排好序的末尾，这个最小的数需要找到它的下标，然后和 arr[i]进行交换

简单选择排序的实现

 public void simpleSort(int[] arr){for(int i = 0; i < arr.length - 1; i++){
            int minIndex = i;
            for(int j = i+1; j < arr.length; j++){if(arr[j] < arr[minIndex]){minIndex = j;}
            }
            swap(arr, i, minIndex);
        }
    }
    public void swap(int[] arr,int i,int j){
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

从代码中我们可以看出，在每一轮比较中（从第一个 for 循环看出一共需要比较 arr.length- 1 轮）通过两两比较寻找剩下的序列中最小的数的下标，然后将 arr[i]与 arr[minIndex]交换，然后下一轮又从 i + 1 开始继续寻找剩下的序列中最小数的下标，这个过程中有的数实际上互相比较了很多次，所以这是一个非常损耗性能的事情

堆排序如何实现

假如给了我们一个数组 arr={4,8,1,0,3,5}, 我们如何通过堆排序来对该数组进行排序呢（由大到小）

步骤如下：

1）将该数组构建成一个最大堆

2）取出最大堆的根节点，维护新堆的最大堆性质，构建一个新的最大堆（堆的大小减一）

3）重复步骤 2，直到取完堆中的所有节点

最后总结一下堆排序的伪代码

大顶堆排序的具体实现 ( 内部由大到小 )： 最后将数组顺序排列

import org.omg.CORBA.RepositoryIdHelper;
 
import java.util.Arrays;
 
public class HeapSort {public static void main(String[] args){HeapSort heapSort = new HeapSort();
        int[] arr = {5, 2, 7, 1, 9, 3};
        //[1, 2, 3, 5, 7, 9]
        heapSort.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
 
 
    private int heapSize = 0;
 
    public void heapSort(int[] arr){
        // 构建一个最大堆
        buildMaxHeap(arr);
        for(int i = arr.length-1; i > 0; i--){swap(arr,i,0);
            heapSize--;
            maxHeapify(arr, 0);
        }
    }
    public void buildMaxHeap(int[] arr){
        heapSize = arr.length;
        // 检查除了叶子节点以外的其他节点是否满足最大堆的性质
        for(int i = (arr.length >> 1) - 1; i >= 0; i--){maxHeapify(arr, i);
        }
 
    }
    public void maxHeapify(int[] arr,int i){
        int leftIndex = 2 * i + 1;
        int rightIndex = 2 * i + 2;
        int largeIndex = i;
        if(leftIndex <heapSize && arr[leftIndex] > arr[i]){largeIndex = leftIndex;}
        if(rightIndex < heapSize && arr[rightIndex] > arr[largeIndex]){largeIndex = rightIndex;}
        if(largeIndex != i){swap(arr, largeIndex, i);
            maxHeapify(arr,largeIndex);
        }
 
    }
 
    public void swap(int[] arr,int i,int j){
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

小顶堆的实现 （* 内部实现 由小到大*）：最后将数组降序排列

import sun.net.www.HeaderParser;
 
import java.util.Arrays;
 
public class SmallHeap {public static void main(String[] args){SmallHeap smallHeap = new SmallHeap();
        int[] arr = {5, 2, 7, 1, 9, 3};
        ///[9, 7, 5, 3, 2, 1]
        smallHeap.smallHeapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
 
 
    int heapSize = 0;
    public void smallHeapSort(int[] arr){buildSmallHeap(arr);
        for(int i = arr.length - 1; i > 0; i--){swap(arr, i, 0);
            heapSize--;
            minHeapify(arr, 0);
        }
    }
 
 
    public void swap(int[] arr,int i,int j){int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    public void buildSmallHeap(int[] arr){
        heapSize = arr.length;
        for(int i =( arr.length >> 1) - 1; i >= 0 ; i--){minHeapify(arr, i);
 
        }
    }
 
    public void minHeapify(int[] arr,int i){
        int leftIndex = 2 * i + 1;
        int rightIndex = 2 * i + 2;
        int minIndex = i;
        if (leftIndex < heapSize && arr[leftIndex] < arr[i]) {minIndex = leftIndex;}
        if (rightIndex < heapSize && arr[rightIndex] < arr[minIndex]) {minIndex = rightIndex;}
        if (minIndex != i) {swap(arr,i,minIndex);
            minHeapify(arr,minIndex);
        }
    }
}

堆的应用——优先队列

最大优先队列（最大堆）

1）insert(S,x): 把 x 插入集合 S 中

2）maximum(S): 返回 S 的最大值

3）extractMax(S)：remove 并且返回 S 的最大值

4）increaseKey(S,i,k): 将 S[i]增加到 K,

应用

作业调度，选出最高优先级的作业执行，随时 insert 一个新的作业到队列

最小优先队列（最小堆）

1）insert(S,x): 把 x 插入集合 S 中

2）minimum(S): 返回 S 的最小值

3）extractMin(S)：remove 并且返回 S 的最小值

4）decreaseKey(S,x,k): 将 S[i]减小到 K,

最大优先队列和最小优先队列的实现

本题的实现：通过最大堆和最小堆分别构建最大优先队列和最小优先队列

import java.util.ArrayList;
 
 
import static java.util.Collections.swap;
public class Solution {
 
    class MaxHeap{ArrayList<Integer> maxHeapList = new ArrayList<Integer>();
        private int maxHeapSize ;
 
        public MaxHeap() {this.maxHeapSize = maxHeapList.size();
        }
    }
    class MinHeap{ArrayList<Integer> minHeapList = new ArrayList<Integer>();
 
        private int minHeapSize ;
 
        public MinHeap() {this.minHeapSize = minHeapList.size();
        }
    }
 
 
 
 
    private int count = 0;
 
    public void Insert(Integer num,MaxHeap maxHeap,MinHeap minHeap){if(count == 0){maxHeap.maxHeapList.add(0,num);
            maxHeap.maxHeapSize++;
        }else {if(count % 2 == 0){if(num > minHeap.minHeapList.get(0)){int temp = extractiMin(minHeap);
                    insertMinHeap(minHeap, num);
                    inserMaxHeap(maxHeap, temp);
                }else {inserMaxHeap(maxHeap,num);
                }
            }else {if(num < maxHeap.maxHeapList.get(0)){int temp = extractMax(maxHeap);
                    inserMaxHeap(maxHeap,num);
                    insertMinHeap(minHeap,temp);
                }else {insertMinHeap(minHeap,num);
 
                }
            }
 
 
        }
 
        count++;
    }
 
    MaxHeap maxHeap = new MaxHeap();
    MinHeap minHeap = new MinHeap();
 
    public void Insert(Integer num) {Insert(num,maxHeap,minHeap);
    }
 
    public int extractiMin(MinHeap minHeap){if(minHeap.minHeapSize < 0) return 0;
        int min = minHeap.minHeapList.get(0);
        minHeap.minHeapList.remove(0);
        // 注意处理 heapsize 的大小
        minHeap.minHeapSize--;
 
        minHeapify(minHeap, 0);
        return min;
    }
 
    // 这里维护最小堆的性质和最大堆不同，比较的是和父节点的大小，因为这里不断的插入新的节点到末尾，应该是和前面的父节点比较
    public void minHeapify(MinHeap minHeap,int i){
        int minIndex = i;
        int parentIndex = (int) Math.floor((i - 1) / 2.0);
        if(parentIndex >= 0 && minHeap.minHeapList.get(i) < minHeap.minHeapList.get(parentIndex) ){
            minIndex = parentIndex;
            swap(minHeap.minHeapList, i, minIndex);
            minHeapify(minHeap,minIndex);
        }
 
    }
 
    public void insertMinHeap(MinHeap minHeap,int num){
        minHeap.minHeapSize++;
        minHeap.minHeapList.add(minHeap.minHeapSize - 1,Integer.MAX_VALUE);
        decreaseKey(minHeap.minHeapList, minHeap.minHeapSize - 1, num);
    }
 
    public void decreaseKey(ArrayList<Integer> list,int i,int key){if(list.get(i) < key)return;
        list.remove(i);
        list.add(i, key);
        minHeapify(minHeap,i);
    }
    public void inserMaxHeap(MaxHeap maxHeap,int num){
 
        maxHeap.maxHeapSize++;
        if(maxHeap.maxHeapSize > 0) {maxHeap.maxHeapList.add(maxHeap.maxHeapSize - 1, Integer.MIN_VALUE);
        }else {maxHeap.maxHeapList.add(0,Integer.MAX_VALUE);
        }
        increaseKey(maxHeap, maxHeap.maxHeapSize - 1, num);
    }
 
    public void increaseKey(MaxHeap maxHeap,int i,int key){if(maxHeap.maxHeapList.get(i) > key)return;
        maxHeap.maxHeapList.remove(i);
        maxHeap.maxHeapList.add(i, key);
        while (i > 0 && maxHeap.maxHeapList.get((int) Math.floor((i-1)/2.0)) < maxHeap.maxHeapList.get(i)){swap(maxHeap.maxHeapList,i,(int) Math.floor((i-1)/2.0));
            i = (int) Math.floor((i - 1) / 2.0);
        }
    }
 
    public int extractMax(MaxHeap maxHeap){if(maxHeap.maxHeapSize < 0)return 0;
        int max = maxHeap.maxHeapList.get(0);
        maxHeap.maxHeapList.remove(0);
        maxHeap.maxHeapSize--;
        maxHeapify(maxHeap, 0);
        return max;
    }
 
    public void maxHeapify(MaxHeap maxHeap,int i){
        int leftIndex = 2 * i +1;
        int rightIndex = 2 * i +2;
        int largeIndex = i;
        if(leftIndex < maxHeap.maxHeapSize && maxHeap.maxHeapList.get(leftIndex) > maxHeap.maxHeapList.get(i)){largeIndex = leftIndex;}
        if(rightIndex < maxHeap.maxHeapSize && maxHeap.maxHeapList.get(rightIndex) > maxHeap.maxHeapList.get(largeIndex)){largeIndex = rightIndex;}
        if(largeIndex != i){swap(maxHeap.maxHeapList,i,largeIndex);
            maxHeapify(maxHeap,largeIndex);
        }
    }
 
    public Double GetMedian() {if(count % 2 == 0){return (maxHeap.maxHeapList.get(0) + minHeap.minHeapList.get(0)) / 2.0;
        }else {return (double)maxHeap.maxHeapList.get(0);
        }
 
    }
 
 
 
}

该题的实现：基于现有的类库：PriorityQueue 实现最大堆和最小堆

import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
 
    private int count = 0;
    // 默认升序排列，也就是默认为最小堆
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 通过重写 Comparator 接口的 compare 方法，构建一个逆序排列的最大堆
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {return o2 - o1;}
    });
 
    public void Insert(Integer num) {if (count %2 == 0) {
            // 最大堆插入一个元素之后，内部会自动重新构建一个最大堆 maxheapify
            maxHeap.offer(num);
            //remove 并返回第一个元素
            int temp = maxHeap.poll();
            // 插入到最小堆，内部同样进行 minheapify
            minHeap.offer(temp);
        } else {minHeap.offer(num);
            int temp = minHeap.poll();
            maxHeap.offer(temp);
        }
        count++;
    }
 
    public Double GetMedian() {if (count %2 == 0) {return new Double((minHeap.peek() + maxHeap.peek())) / 2;
        } else {return new Double(minHeap.peek());
        }
    }
 
}

参考

《剑指 offer 纪念版》

《算法导论第三版》

正文完
堆排序
发表至：无分类
2019-07-18
 0