4. Median of Two Sorted Arrays

我不是很明白，为何这道题会被标记为hard。。。感觉挺简单的啊，求两个已经排序的数组的中位数。

对于排序，有个很经典的题目，将两个排好序的数组合并。这道题也是类似，而且都不必完全合并，只要知道中位数是合并后的第几个元素就可以了。如果合并后的长度是偶数，中位数就是中间两个元素的平均数；如果合并后长度是奇数，中位数就是中间的元素。

hard可能是因为要处理各种边界条件吧。

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 基本思想是将nums1和nums2合并下，再计算中位数
        int length = nums1.length + nums2.length;
        boolean odd = length % 2 == 1;  // 合并后的长度是否是奇数？
        // 这两个flag用于表示数组是否已经遍历完毕
        boolean flag1 = nums1.length > 0, flag2 = nums2.length > 0;
        long sum = 0;   // 中位数可能是2个数字的和，leetcode中如果求2个int的和，记得用long，因为可能溢出。。。被坑了好多次。。。
        int i = 0, j = 0, count = 0;  // i、j分别表示nums1和nums2的下标，count表示当前总共已经遍历了多少个元素

        while (flag1 || flag2) {
            int currentValue = 0;
            // 如果当前元素是来自nums1
            if (flag1 && (!flag2 || nums1[i] <= nums2[j])) {
                currentValue = nums1[i];
                i++;  // 有点类似list中的current=current.next
                count++;
                flag1 = i < nums1.length;
            }
            // 如果当前元素是来自nums2
            else if (flag2 && (!flag1 || nums1[i] > nums2[j])) {
                currentValue = nums2[j];
                j++;
                count++;
                flag2 = j < nums2.length;
            }
            //System.out.println(currentValue);

            // 无论合并后的长度是偶数还是奇数，length / 2 + 1这个元素都是要计算的，而且这个元素之后的都不用再考虑了
            if (count == length / 2 + 1) {
                sum += currentValue;
                break;
            }
            // 只有是偶数时，才需要length / 2这个元素
            if (count == length / 2 && !odd) {
                sum += currentValue;
            }
        }

        if (!odd) {  // 偶数时，中位数是中间2个元素的和
            return (double) sum / 2;
        } else {   // 奇数时，中位数就是中间的那个元素
            return sum;
        }
    }
}