findingsea's Studio.

Median of Two Sorted Arrays@LeetCode

LeetCode
Word count: 316 / Reading time: 2 min
2015/03/23 Share

Median of Two Sorted Arrays

这题记得当时也是查了网上的资料才做出来的，而且采用的是一个通用算法findKth。

其实思想很简单：要寻找第k小的元素，那么总是保持数组A的当前元素（即A[a]）为当前最小元素（如果不是，则交换A和B数组，使这一条成立），然后弹出该元素（即++a），然后再递归调用寻找第k-1小的元素。

这需要注意的地方在于：

  • A.length + B.length为偶数的时候，中位数有两个，要取平均。
  • A.length + B.length为奇数的时候，中位数只有一个。

实现代码如下：

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
/**
 * Created by findingsea on 14/11/16.
 */
public class Solution {
    public double findKth(int A[], int a, int B[], int b, int k) {
        if (A.length == a || (b < B.length && A[a] > B[b])) {
            int tmp[] = A;
            A = B;
            B = tmp;
            int t = a;
            a = b;
            b = t;
        }
        if (k == 1) return A[a];
        return findKth(A, ++a, B, b, --k);
    }
    public double findMedianSortedArrays(int A[], int B[]) {
        int len = A.length + B.length;
        if (len == 1) return A.length == 0 ? B[0] : A[0];
        if (len % 2 == 0) {
            return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2;
        }
        else {
            return findKth(A, 0, B, 0, len / 2 + 1);
        }
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/03/23/median-of-two-sorted-arrays/

发表日期: March 23rd 2015, 9:18:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 100
2020
2019
2018
2017
2015
2014
2013
Octopress GitHub Python Django 吐槽 Reading ACM 项目总结 JavaScript 日志 Java LeetCode Interview Algorithm Life Windows ffmpeg life Go c++ essay review