4. Median of Two Sorted Arrays

Thinking:

• Method1: Merge two sorted arrays to one and take the median of the arrayList.

	class Solution {
	    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	        if(nums1.length == 0 && nums2.length != 0){
	            int size = nums2.length / 2;
	            if(nums2.length % 2 == 0){
	                return (nums2[size - 1] + nums2[size]) / 2.0d;
	            }else{
	                return nums2[size];
	            }
	        }
	        if(nums2.length == 0 && nums1.length != 0){
	            int size = nums1.length / 2;
	            if(nums1.length % 2 == 0){
	                return (nums1[size - 1] + nums1[size]) / 2.0d;
	            }else{
	                return nums1[size];
	            }
	        }
	        if(nums2.length == 0 && nums1.length == 0){
	            return 0.0d;
	        }
	        List<Integer> list = new ArrayList<>();
	        int index1 = 0;
	        int index2 = 0;
	        int complete = 0;
	        while(index1 < nums1.length && index2 < nums2.length){
	            if(nums1[index1] <= nums2[index2]){
	                list.add(new Integer(nums1[index1]));
	                index1++;
	            }else{
	                list.add(new Integer(nums2[index2]));
	                index2++;
	            }
	            if(index1 == nums1.length){
	                complete = 1;
	            }else if(index2 == nums2.length){
	                complete = 2;
	            }
	        }
	        if(complete == 1){
	            for(; index2 < nums2.length; index2++){
	                list.add(new Integer(nums2[index2]));
	            }
	        }else{
	            for(; index1 < nums1.length; index1++){
	                list.add(new Integer(nums1[index1]));
	            }
	        }
	        int size = list.size();
	        if(size % 2 == 0){
	            return (list.get(size/2 - 1) + list.get(size/2)) / 2.0d;
	        }else{
	            return list.get(size/2);
	        }
	    }
	}

二刷

• Method 1
  1. 使用merge将两个数组合并起来。
  2. 根据奇数或是偶数，返回中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int first = 0, second = 0;
        int[] merge = new int[len1 + len2];
        int count = 0;
        while(first < len1 || second < len2){
            if(first < len1 && second < len2)
                merge[count++] = nums1[first] <= nums2[second] ? nums1[first++]: nums2[second++];
            else if(first < len1)
                merge[count++] = nums1[first++];
            else
                merge[count++] = nums2[second++];
        }
        return (len1 + len2) % 2 != 0 ?
            (double)merge[(len1 + len2) / 2] :
        ((double)merge[(len1 + len2) / 2] + (double)merge[(len1 + len2) / 2 - 1]) / 2;
    }
}

• Method 2
  1. 将两个数组合并起来，再排序。
  2. 根据奇数偶数来去除中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merge = new int[nums1.length + nums2.length];
        int i = 0;
        for(i = 0; i < nums1.length; i++)
            merge[i] = nums1[i];
        for(; i - nums1.length < nums2.length; i++)
            merge[i] = nums2[i - nums1.length];
        Arrays.sort(merge);
        return (merge.length) % 2 != 0 ?
            (double)merge[merge.length / 2] : (double)(merge[merge.length / 2] + merge[merge.length / 2 - 1]) / 2;
    }
}