算法通关村第十四关黄金挑战——堆解决数据流的中位数和数组求中位数的方法总结

关注微信公众号：怒码少年。回复关键词【电子书】，领取多本计算机相关电子书
遇到任何问题都可以在后台向我提问，完全免费！！大家共同进步！！

大家好，我是怒码少年小码。

本篇主要是讲讲如何利用堆来求一个数组的中位数，以及求数组中位数的常见方法主题。

数据流的中位数

LeetCode 295：中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [1,2,3,4] 的中位数是 (2 + 3) / 2 = 2.5 。

分析：观察数组，偶数情况下，把数组分成两份，中位数就是前半数组的最大值和后半数组的最小值的平均值。

因此，我们可以创建一个最小堆和最大堆，分别保存数组的较小的那一部分和数组中较大的一部分。要求最小堆的元素数量>= 最大堆的元素数量，两个堆中的元素数量相差不大于一个元素：

• 两个堆中的元素数量相等。表示数组元素总数是偶数——中位数是最小堆和最大堆的堆顶元素的平均值。
• 两个堆中的元素数量不相等（最小堆的元素数量>最大堆的元素数量）。表示数组元素总数是奇数——中位数是最小堆的堆顶元素。

堆的构建在C++和python中太麻烦，这里我们利用Java中的优先队列``来解决

PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;

public MedianFinder() {
    this.minHeap = new PriorityQueue<>();
    this.maxHeap = new PriorityQueue<>((a,b)->b-a);
}
    
public void addNum(int num) {
    //num比minHeap的最小值大，说明它可以插入到最小堆中
    if(minHeap.isEmpty() || num > minHeap.peek()){
        minHeap.offer(num);
        //minHeap中的元素个数比maxHeap多2个元素，就平衡一下
        if(minHeap.size()-maxHeap.size() > 1){
            maxHeap.offer(minHeap.poll());
        }
    }else{
        maxHeap.offer(num);
        //确保多的那一个元素一定在最小堆，也就是总数是奇数的时候，中间值在最小堆中
        if(maxHeap.size() > minHeap.size() ){
            minHeap.offer(maxHeap.poll());
        }
    }
}
    
public double findMedian() {
    if(minHeap.size() > maxHeap.size()){
        return minHeap.peek();
    }else{
        return (minHeap.peek() + maxHeap.peek()) / 2.0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

求数组中位数的方法总结

排序法：

利用某种排序算法将数组进行排序，然后根据数组长度的奇偶性确定中位数的位置。如果数组长度为奇数，中位数即为排序后的中间元素；如果数组长度为偶数，中位数为排序后中间两个元素的平均值。

import java.util.Arrays;

public class Median {
    public static double findMedian(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        if (n % 2 == 0) {
            return (nums[n / 2 - 1] + nums[n / 2]) / 2.0;
        } else {
            return nums[n / 2];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

堆法：

(就是上面写的方法)利用最大堆和最小堆，将数组分成两部分。最大堆存储较小的一部分元素，最小堆存储较大的一部分元素。如果两个堆的大小相等，则中位数为两个堆顶元素的平均值；否则，中位数为较大堆的堆顶元素。

双指针法：

对数组进行两端指针的遍历。在遍历过程中，根据条件将指针向中间移动，直到找到中位数。这种方法适用于已经有序或部分有序的数组。

import java.util.Arrays;

public class Median {
    public static double findMedian(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            left++;
            right--;
        }
        if (left == right) {
            return nums[left];
        } else {
            return (nums[left] + nums[right]) / 2.0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

快速选择算法：

基于快速排序的思想，通过每次选择一个元素作为基准点将数组分成两部分，然后根据基准点的位置继续递归搜索中位数所在的部分，直到找到中位数。

import java.util.Random;

public class Median {
    public static double findMedian(int[] nums) {
        int n = nums.length;
        if (n % 2 == 0) {
            return (quickSelect(nums, 0, n - 1, n / 2 - 1) + quickSelect(nums, 0, n - 1, n / 2)) / 2.0;
        } else {
            return quickSelect(nums, 0, n - 1, n / 2);
        }
    }

    private static int quickSelect(int[] nums, int left, int right, int k) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) {
            return nums[k];
        } else if (pivotIndex < k) {
            return quickSelect(nums, pivotIndex + 1, right, k);
        } else {
            return quickSelect(nums, left, pivotIndex - 1, k);
        }
    }

    private static int partition(int[] nums, int left, int right) {
        int randomIndex = new Random().nextInt(right - left + 1) + left;
        swap(nums, randomIndex, right);
        int pivot = nums[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, right);
        return i + 1;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

END

关关难过，关关过！算法就是要长期练习！大家加油！！

关注微信公众号：怒码少年。
遇到任何问题都可以在后台向我提问，完全免费！！大家共同进步！！