Share my AC JAVA solution


  • 1
    W
    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            int k = (m + n) / 2 + 1;
            double x = (double) kth(nums1, 0, m - 1, nums2, 0, n - 1, k);
            if ((m + n) % 2 == 0) {
                double y = (double) kth(nums1, 0, m - 1, nums2, 0, n - 1, k - 1);
                return (x + y) / 2;
            }
            return x;
        }
        private int kth(int[] a, int a_start, int a_end, int[] b, int b_start, int b_end, int k) {
            if (a_start > a_end) return b[b_start + k - 1];
            if (b_start > b_end) return a[a_start + k - 1];
            
            int a_mid = a_start + (a_end - a_start) / 2;
            int b_mid = b_start + (b_end - b_start) / 2;
            int x = a_mid - a_start + 1;
            int y = b_mid - b_start + 1;
                
            if (a[a_mid] <= b[b_mid]) {
                if (k < x + y) {
                    return kth(a, a_start, a_end, b, b_start, b_mid - 1, k);
                } else {
                    return kth(a, a_mid + 1, a_end, b, b_start, b_end, k - x);
                }
            } else {
                if (k < x + y) {
                    return kth(a, a_start, a_mid - 1, b, b_start, b_end, k);
                } else {
                    return kth(a, a_start, a_end, b, b_mid + 1, b_end, k - y);
                }
            }
        }
    }

  • 0
    J

    This solution's runtime is not O(log(m+n)), because it only reduce one array's size in each iteration.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.