Kevin's Blog
0%

LeetCode No4 Median of Two Sorted Arrays

发表于

题目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数

示例

1
2
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
1
2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
1
2
Input: nums1 = [2], nums2 = []
Output: 2.00000

思路

我的解法思路：定义一个数组，长度为两个之和，然后将其排序到对应位置求解（暴力解法不可取）

解法1 我的解法（Bad）

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int l1 = nums1.length;
    int l2 = nums2.length;
    int[] nums3 = new int[l1 + l2];
    int n1 = 0, n2 = 0;
    double out;
    for (int i = 0; i < l1 + l2; i++) {
        if (n1 > l1 - 1) {  //nums1已经复制完毕，直接对nums2复制，break
            System.arraycopy(nums2,n2,nums3,i,l2-n2);
            break;
        }
        if (n2 > l2 - 1) {  //同上
            System.arraycopy(nums1,n1,nums3,i,l1-n1);
            break;
        }
        if (nums1[n1] >= nums2[n2]) {
            nums3[i] = nums2[n2];
            n2++;
        }
        else {
            nums3[i] = nums1[n1];
            n1++;
        }
    }
    if ((l1+l2)%2 == 1) {  //判断怎么取中位数，奇数取中间元素，偶数取中间两个元素平均值
        int pos = (nums3.length-1)/2;
        out = nums3[pos];
    } else {
        int pos = nums3.length / 2 -1;
        out = ((double)(nums3[pos] + nums3[pos + 1])) / 2;
    }
    return out;
}

标准解法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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int index1 = 0;
    int index2 = 0;
    int med1 = 0;
    int med2 = 0;
    
    //太强了，没想到还可以这个样子
    for (int i=0; i<=(nums1.length+nums2.length)/2; i++) { 
        //因为要取中间值，所以大于中间值的可以全部丢弃
        med1 = med2;
        if (index1 == nums1.length) { //nums1已经遍历完成，但还没达到条件，所以中间值的都在nums2里面
            med2 = nums2[index2];
            index2++; //与med1交替取值，最后output
        } else if (index2 == nums2.length) {
            med2 = nums1[index1];
            index1++; //同上
        } else if (nums1[index1] < nums2[index2] ) {
            med2 = nums1[index1]; //
            index1++;
        }  else {
            med2 = nums2[index2];
            index2++;
        }
    }

    // the median is the average of two numbers
    if ((nums1.length+nums2.length)%2 == 0) {
        return (float)(med1+med2)/2;
    }
    return med2;
}

想法

我的解法用了数组，而解法2只用了两个变量，空间省了很多，因为数组的缘故，我在进行赋值时会调用System.arraycopy函数，在时间上拖慢了很多，学到了，真的是学到了。

标准解法3 分而治之

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int sum = m + n;
    if (sum % 2 == 0) {
        return (findKth(nums1,0,nums2,0,sum / 2)+findKth(nums1, 0, nums2, 0, sum / 2 + 1))/ 2.0;
    } else {
        return findKth(nums1, 0, nums2, 0, sum / 2 + 1) * 1.0;
    }
}

private int findKth(int[] a, int startA, int[] b, int startB, int k) {
    if (startA >= a.length) {
        return b[startB + k - 1];
    }
    if (startB >= b.length) {
        return a[startA + k - 1];
    }
    if (k == 1) {
        return Math.min(a[startA], b[startB]);
    }
    // start to throw away k/2 length array in either a or b
    int midA = (startA + k / 2 - 1 >= a.length) ? Integer.MAX_VALUE : a[startA + k / 2 - 1];
    int midB = (startB + k / 2 - 1 >= b.length) ? Integer.MAX_VALUE : b[startB + k / 2 - 1];
    if (midA > midB) {
        return findKth(a, startA, b, startB + k / 2, k - k / 2);
    } else {
        return findKth(a, startA + k / 2, b, startB, k - k / 2);
    }
}