4. Median of Two Sorted Arrays (Hard)

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

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)).

You may assume nums1 and nums2 cannot be both empty.

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

Hints

Solutions

  • Java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1_len = nums1.length;
        int nums2_len = nums2.length;

        int total_len = nums1_len + nums2_len;
        boolean isOdd = true;
        if (total_len % 2 == 0) isOdd = false;

        int[] tmp = new int[total_len];

        int count = 0;
        int i = 0, j = 0;
        while(count < total_len) {
            if (i < nums1_len && j < nums2_len && nums1[i] <= nums2[j]) {
                tmp[count++] = nums1[i++];
            }

            if (i < nums1_len && j < nums2_len && nums1[i] >= nums2[j]) {
                tmp[count++] = nums2[j++];
            }

            if (j == nums2_len && i < nums1_len) {
                tmp[count++] = nums1[i++];
            }

            if (i == nums1_len && j < nums2_len) {
                tmp[count++] = nums2[j++];
            }

            // pruning
            if (total_len >= 3 && count > (total_len + 1) / 2) {
                break;
            }
        }

        if (isOdd) {
            return tmp[(total_len-1)/2];
        }

        return (tmp[total_len/2] + tmp[total_len/2-1]) / 2.0;
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-04-22 10:43:11

results matching ""

    No results matching ""