每日一题——求无序数组的中位数

发表于 | 分类于

题目

给定一个非空的无需数组，输出该数组的中位数

例如：

1
2
输入：[8,13,7,21,15,20,30,9]
输出：14

思路一

首先我们想到的就是对数组进行排序，然后再求中位数，但是排序算法中最好快速排序时间复杂度为O(nlogn)

我们可以换一种思路，什么叫中位数？

中位数我们可以理解为它的左半部分比它小，它的右半部分比它大。说到这里，有没有感觉这种情况好像在哪实现过呢？没错，快速排序使用partition进行分区的时，最好的情况下会使数据分为两部分

所以我们可以将这道题升级为TOP N问题，通过调用快排的partition函数，找到中位数。

怎么利用partition函数呢？

1
int partition(int[] arr, int start, int end);

partition返回的是下标pivot，如果返回的下标pivot刚好等于中位数的下标，则直接返回值

如果pivot>midIdx， 往左边找，让end = pivot-1；

如果pivor<midIdx，往右边找，让end = pivot+1；

如果数组的个数是奇数，那么只要找到下标为 length/2 位置的pivot就是我们要找的中位数。如果数组的个数是偶数，那也简单，找到下标为 (length/2)-1 和 length/2

伪代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package algorithm;

import java.util.Arrays;

/**
 * Created by linnanwei on 2019/9/3
 *
 * @author linnanwei
 */
public class ArrayMedian2 {
    public double findMedianInArray(int[] arr){
        if (arr == null || arr.length==0){
            return 0;
        }
        int length = arr.length;
        int start = 0;
        int end = length-1;
        // 长度为奇数的情况
        if (length%2 == 1){
            int medianIdx = length/2;
            return doFindMedian(arr, start, end, medianIdx);
        }
        // 长度为偶数的情况
        else{
            int medianIdx1 = length/2 - 1;
            int medianIdx2 = length/2;
            // 这里要注意，因为第一次查找中位数时，已经做了分割，所以直接查找后面即可
            return (doFindMedian(arr, start, end, medianIdx1)+doFindMedian(arr, medianIdx1+1, end, medianIdx2)) / 2.0;
        }
    }

    private double doFindMedian(int[] arr, int start, int end, int medianIdx){
        while(true){
            int pivot = partition(arr, start, end);
            if (pivot == medianIdx){
                return arr[pivot];
            }
            else if (pivot > medianIdx){
                end = pivot - 1;
            }
            else {
                start = pivot + 1;
            }
        }
    }

    public int partition(int[] arr, int start, int end){
        int pivot = arr[start];
        int idx = start+1;
        for (int i = start+1; i <= end ; i++) {
            if (arr[i] < pivot){
                swap(arr, i, idx);
                idx++;
            }
        }
        swap(arr, start, idx-1);
        return idx-1;
    }

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

    public static void main(String[] args) {
        int[] arr = {4,5,2,3,1,6};
        ArrayMedian2 arrayMedian2 = new ArrayMedian2();
        // System.out.println(arrayMedian2.partition(arr, 0, arr.length-1));
        System.out.println(arrayMedian2.findMedianInArray(arr));
    }
}

时间复杂度分析

partition的时间复杂度为O(n)，如果一次没找到，理想情况下，下次从n/2个中寻找

所以O(n) = O(n) + O(n/2) + O(n/4) … +O(1)

所以时间复杂度为O(n)，但是这只是理想情况，最差的时间复杂度有可能蜕变为O(n^2)

思路二

还有一种更好的解决方案，使用两个堆数据结构。我们通过维护一个大堆和一个小堆，小堆的元素都比大堆中的元素大

1、刚开始往大顶堆中插入数据

2、插入的数据如果比大顶堆大，则插入到小顶堆

3、插入的数据如果比大顶堆的堆顶元素小，则插入到大顶堆

4、大顶堆元素的个数要大于等于小顶堆的元素，但是不能比小顶堆多于1个，如果大顶堆中的元素个数比小顶堆多出1个以上，则弹出堆顶元素到小顶堆中

5、如果小顶堆的元素个数大于大顶堆，弹出小顶堆元素到大顶堆

如果数组元素个数为奇数，直接弹出大顶堆堆顶元素

如果数组元素个数为偶数，弹出大顶堆和小顶堆元素之和除以2

画个图开心一下

1

2

3

4

5

6

PS：原谅我第一次画图……

代码实现

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package algorithm;

import java.util.PriorityQueue;

/**
 * 无序数组中的中位数
 * @author SouthLight-Lin
 */
public class ArrayMedian {
	/**
	 * 解题思路：
	 * 		如果数组个数是奇数个，那么中位数是排序后数组的中间值
	 * 		如果数组个数是偶数个，那么中位数是排序后数组的中间两个数的均值
	 * 		使用两个堆，一个是最大堆left，一个是最小堆right
	 * 		right中所有的元素都比left大
	 * 	
	 */
	
	/** 大顶堆，存储左半边元素 **/
	private PriorityQueue<Integer> left = new PriorityQueue<Integer>((o1, o2)->{
		return o2 -o1;
	});
	
	/** 小顶堆，存储右半边元素  **/
	private PriorityQueue<Integer> right = new PriorityQueue<Integer>();
	
	/** 当前数据流读入的元素 **/
	private int N = 0;
	
	/** 插入元素的同时维护两个堆结构 **/
	public void insert(Integer val){
		// 如果比大顶堆的堆顶元素大，插入到小顶堆
		if (left.size() == 0 || val <= left.peek()){
			left.add(val);
		}
		else{
			right.add(val);
		}
		N++;
		adjust();
	}
	/** 调整两个堆得数量以达到平衡 **/
	private void adjust() {
		if (right.size() > left.size()){
			left.add(right.poll());
		}
		else if (left.size() - right.size() > 1){
			right.add(left.poll());
		}
	}

	public double getMedian(){
		if(N%2==0){
			return (left.peek()+right.peek())/2.0;
		}else{
			return right.peek();
		}
	}


	public static void main(String[] args) {
		int[] data = {8,13,7,21,15,20,30,9};
		ArrayMedian arrayMedian = new ArrayMedian();
		for(int i:data){
			arrayMedian.insert(i);
		}
		
		System.out.println(arrayMedian.getMedian());
	}
}

时间复杂度分析

遍历数据为O(n)，调整堆的复杂度为O(log n/2)

所以时间复杂度为O(n*log n/2)，n不是很大时，可以看成为O(n)，稳定性比第一种方案好点