package 数组;
import java.lang.reflect.Array;
import java.util.ArrayList;
/**
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 * 
 * @author Huangyujun
 *
 */
public class _4_寻找两个正序数组的中位数 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 重新再排序成一个新数组，然后找中间的
        int m = nums1.length;
        int n = nums2.length;
        int num1_len = m;
        int num2_len = n;
        ArrayList<Double> list = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (m != 0 && n != 0) {
            if (nums1[i] < nums2[j]) {
                list.add((double) nums1[i++]);
                m--;
            } else {
                list.add((double) nums2[j++]);
                n--;
            }
        }
        int start1 = num1_len - m;
        while (m != 0) { // nums1 还有剩下的
            list.add((double) nums1[start1++]);
            m--;
        }
        int start2 = num2_len - n;
        while (n != 0) { // nums2 还有剩下的
            list.add((double) nums2[start2++]);
            n--;
        }
        if (list != null) {
            int len = list.size();
            if (len % 2 == 0) {
                int mid = len / 2;
                return (list.get(mid - 1).doubleValue() + list.get(mid).doubleValue()) / 2;
            } else {
                int mid = list.size() / 2;
                return list.get(mid).doubleValue();
            }
        }
        return -1;
    }
}