LeetCode 4. Median of Two Sorted Arrays

Description

https://leetcode.com/problems/median-of-two-sorted-arrays/

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

Example 1:

Example 2:

Explanation

This is a classical coding interview question. Hard and worth thinking.

We can convert the problem to the problem of finding kth element after merging Array A and B, where k is (Array A’s length + Array B’ Length) / 2.

  • If any of the two arrays is empty, then the kth element is the non-empty array’s kth element.
  • If k == 1, the kth element is the first element of A or B.
  • For all other cases, we compare the (k / 2) th number in A and the (k / 2) th number in B. If the array has no more than k /2 elements, we set key = MAX_VALUE. If keyA < keyB, we get rid of first k /2 elements. We keep searching in the remainder for the (k – k /2) th element.

Video Tutorial

Java Solution

One thought

Leave a Reply

Your email address will not be published. Required fields are marked *