dcddc

西米大人的博客

0%

两个排序数组的中位数

发表于 更新于 分类于 热度: ℃ 评论: ℃
字数： 301 阅读时长 ≈ 1 分钟
lintcode算法

题目描述

两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。

思路

  • 我的笨办法
    因为两数组已经排序了，所以先求两数组合并后的中位数下标i，然后从头开始比较比较两个数组，直到找到下标为i的中位数为止。
    注意，需要分合并后的数组元素个数为奇数还是偶数，因为偶数返回的中位数是中间两个数的平均值。

  • 别人的高端分治法
    回想归并排序，本质上是先排序好子数组，再将子数组合并排序

    所以，可以这样：

  • 先求A和B数组的中位数，再比较中位数：

  • 中位数相等，直接输出

  • A的中位数更大，则取A的左半部分和B的右半部分

  • B的中位数更大，则取A的右半部分和B的左半部分

  • 再来一遍…

代码

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
73
74
75
76
77
78
79
80
81
82
private int midIndex; 
    public double findMedianSortedArrays(int[] A, int[] B) {
        int length = A.length + B.length;
		if(length % 2 == 0) {
			midIndex = (length / 2);
			return getMid(false, A, B);
		} else {
			midIndex = ((length+1) / 2);
			return getMid(true, A, B);
		}
		
    }
	

	private double getMid(boolean isSingle, int[] A, int[] B) {
		if(A.length == 0) {
			if(isSingle) {
				return B[midIndex-1];
			}else {
				return (double)(B[midIndex]+B[midIndex-1]) / 2;
			}
		}else if (B.length == 0) {
			if(isSingle) {
				return A[midIndex-1];
			}else {
				return (double)(A[midIndex]+A[midIndex-1]) / 2;
			}
		}else {
			int tmp = 0;
			int tmpCount = 1;
			int left = 0;
			int i = 0;
			int j = 0;
			if(isSingle) {
				while(tmpCount <= midIndex) {
					if(A[i] >= B[j]) {
						tmp = B[j];
						if(j < B.length-1) {
						    j++;
						}else{
						    B[j] = Integer.MAX_VALUE;
						}
					}else {
						tmp = A[i];
						if(i < A.length-1) {
						    i++;
						}else{
						    A[i] = Integer.MAX_VALUE;
						}
					}
					
					tmpCount++;
				}
				return tmp;
			} else {
				while(tmpCount <= midIndex+1) {
					if(A[i] >= B[j]) {
						tmp = B[j];
						if(j < B.length-1) {
						    j++;
						}else{
						    B[j] = Integer.MAX_VALUE;
						}
					}else {
						tmp = A[i];
						if(i < A.length-1) {
						    i++;
						}else{
						    A[i] = Integer.MAX_VALUE;
						}
					}
					
                    if(tmpCount == midIndex) {
						left = tmp;
					}
					
					tmpCount++;
				}
				return (double)(left+tmp)/2;
			}
		}
	}

考察点

  • 分治法