4. Median of Two Sorted Arrays

Description

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

code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0, j = 0;
        // 记录当前已经判断的数量
        int count = 0;
        int m = nums1.length, n = nums2.length;
        // 记录两个数组之和为奇数还是偶数
        boolean isEven = (m + n) % 2 == 0;
        // 记录中位数应该是为第几个数
        int median = (m + n) / 2;
        // 记录中位数的和
        double sum = 0;
        // 记录当前改变的数
        int t = 0;
        while (i < m || j < n) {
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    t = nums1[i];
                    ++i;
                }
                else {
                    t = nums2[j];
                    ++j;
                }
            } else if (i < m) {
                t = nums1[i];
                ++i;
            } else if (j < n) {
                t = nums2[j];
                ++j;
            }
            ++count;
            if (count == median && isEven) {
                sum += t;
            } else if (count == median + 1) {
                sum += t;
            }
        }
        return isEven ? sum / 2 : sum;
    }
}