Median of Two Sorted Arrays

LC 4

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

解题指导： 注意变形为kth element

public class Solution {
     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // method1 heap, o(m＋n）
        // method2 kth element
        if ( nums1 == null && nums2 == null) return 0;
        int len = nums1.length + nums2.length;
        if (len % 2 == 1){
            // 第len／2+1 个元素，因为index本身是len／2
            return findKth(nums1, 0, nums2, 0, len / 2 + 1);
        }else {
             // index 本身是len/2－1， len／2
            return (findKth(nums1, 0, nums2, 0, len / 2 ) + findKth(nums1, 0, nums2, 0, len / 2 + 1 )) / 2.0;
        }

    }

    //
    public double findKth(int[] nums1, int nums1_start, int[] nums2, int nums2_start, int k ){
        if ( nums1_start  >= nums1.length)     return nums2[nums2_start + k - 1];
        if ( nums2_start >= nums2.length) return nums1[nums1_start + k - 1];
        //
        if ( k == 1) return Math.min(nums1[nums1_start],nums2[nums2_start]);
        int nums1_key = nums1_start + k / 2 - 1 < nums1.length
                    ? nums1[nums1_start + k / 2 - 1]
                    : Integer.MAX_VALUE;

        int nums2_key = nums2_start + k / 2 - 1 < nums2.length
                    ? nums2[nums2_start + k / 2 - 1]
                    : Integer.MAX_VALUE;
        if( nums1_key > nums2_key){
            return findKth(nums1, nums1_start, nums2, nums2_start + k / 2 , k - k / 2);
        }else {
            return findKth(nums1, nums1_start + k / 2, nums2, nums2_start, k - k / 2);
        }

    }
}

Heap 写法

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Collections.reverseOrder());
        int counts = nums1.length + nums2.length;
        boolean isDouble = false;
        if (counts % 2 == 0) {
            isDouble = true;
        }
        int index = counts / 2; 
        int j = 0;
        int m = 0;
        int i = 0;
        for (; i <= index && j < nums1.length && m < nums2.length; i++) {
            if (nums1[j] < nums2[m]) {
                heap.add(nums1[j]);
                j++;
            } else {
                heap.add(nums2[m]);
                m++;  
            }
        }

        while (j < nums1.length && i <= index) {
            heap.add(nums1[j]);
            j++;
            i++;
        }

        while (m < nums2.length && i <= index) {
            heap.add(nums2[m]);
            m++;
            i++;
        }

        if (isDouble) {
            return (heap.poll() + heap.poll()) / 2.0;
        } else {
            return (double)heap.poll();
        }

    }