p4

发表于 | 分类于 |

LeetCode p4 Median of Two Sorted Arrays 题解

1.题目：

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题意：

输入两个排好序的数组，求将两个数组有序合并之后中间的数值，如果有两个数则输出他们的平均值。

2.解题思路:

首先将两种取中间值的情况，合并成一种情况。
int l1 = nums1.length;
int l2 = nums2.length;
int a = (l1 + l2 + 1) / 2;
int b = (l1 + l2 + 2) / 2;
即取第a个数,第b个数的平均值即可。
然后将题目转换成为取两个数组合并后的第K个数，即getk函数所做的事。
getk这个函数，采用二分的方式一步步排除K前面的数，直到获得第K个数。
排除方式：两个数组：num1,nums2，每次分别取出未排除个数的1/2。
则取出的数中哦你总有一半会需要整体排除，即可一步步逼近K。
注意边界条件。

3.代码

[title] [] [url] [link text]
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
 
public class Solution {
    public int getk(int[] nums1, int starta, int[] nums2, int startb, int k) {
        if (starta > nums1.length - 1) return nums2[startb + k - 1];
        if (startb > nums2.length - 1) return nums1[starta + k - 1];
        if (k == 1) return Math.min(nums1[starta], nums2[startb]);
        int mid1 = nums1.length - 1;
        int mid2 = nums2.length - 1;
        int d1 = nums1[mid1];
        int d2 = nums2[mid2];
        if (starta + k / 2 - 1 < nums1.length) {
            mid1 = starta + k / 2 - 1;
            d1 = nums1[mid1];
        }
        if (startb + k / 2 - 1 < nums2.length) {
            mid2 = startb + k / 2 - 1;
            d2 = nums2[mid2];
        }
        if (d1 > d2) return getk(nums1, starta, nums2, mid2 + 1, k - mid2 + startb - 1);
        else return getk(nums1, mid1 + 1, nums2, startb, k - mid1 + starta - 1);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double i = 0;
        int l1 = nums1.length;
        int l2 = nums2.length;
        int a = (l1 + l2 + 1) / 2;
        int b = (l1 + l2 + 2) / 2;

        double a1 = getk(nums1, 0, nums2, 0, a);
        double a2 = getk(nums1, 0, nums2, 0, b);
        return (a1 + a2) / 2;

    }
}

4.一些总结：