leetcode-median-of-two-sorted-arrays

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/median-of-two-sorted-arrays/

　　求两个有序数组的中位数，时间复杂度要求是log(m+n)

题目分析

　　单个数组中位数的问题的讨论见我之前一篇博客

　　思路参考了这里：https://discuss.leetcode.com/topic/28602/concise-java-solution-based-on-binary-search 先把问题转化成两个有序数组的第k小的元素。nums1的长度是l1，nums2的长度是l2，如果要找第k小的元素，可以先这样考虑，分别取nums1和nums2的第k / 2个元素，不妨设为a和b，显而易见，两个数组中的第k小的元素不可能同时小于a和b，而且如果a < b的话，那么a以及nums1中a之前的元素都可以舍弃掉了，这样问题由k降了一半，最后复杂度是o(log(m + n))，当然边界和特殊情况是要做处理的。

代码

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
public class Solution {
    
    private int l1;
    private int l2;
    private double findkth(int[] nums1, int s1, int[] nums2, int s2, int k) {
        if (s1 >= l1) {
            return nums2[s2 + k - 1];
        }
        if (s2 >= l2) {
            return nums1[s1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int s1Mid = Integer.MAX_VALUE;
        int s2Mid = Integer.MAX_VALUE;
        if (s1 + k / 2 - 1 < l1) {
            s1Mid = nums1[s1 + k / 2 - 1];
        }
        if (s2 + k / 2 - 1 < l2) {
            s2Mid = nums2[s2 + k / 2 - 1];
        }
        if (s1Mid < s2Mid) {
            return findkth(nums1, s1 + k / 2, nums2, s2, k - k / 2); //注意最后一个参数一定是k-k/2，不然k为奇数时会漏掉一个数
        } else {
            return findkth(nums1, s1, nums2, s2 + k / 2, k - k / 2);
        }
    }
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        l1 = nums1.length;
        l2 = nums2.length;
        int len = l1 + l2;
        if (len % 2 == 1) {
            return findkth(nums1, 0, nums2, 0, len / 2 + 1);
        } else {
            return (findkth(nums1, 0, nums2, 0, len / 2) + findkth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
        }
    }
}