LeetCode 4. Median of Two Sorted Arrays

LeetCode problem No.4.

No.3 is here.

modalsoul.hatenablog.com

4. Median of Two Sorted Arrays

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

You may assume nums1 and nums2 cannot be both empty.

Example

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Code

object Solution {
    def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
        val totalSize = nums1.length + nums2.length
        val index:Int = totalSize/2
        val connected = (nums1 ++ nums2).sorted
        if(totalSize % 2 == 0) (connected(index) + connected(index-1))/2.0
        else connected(index)
    }
}

Methods

• Calculate median index from m and n.
• Make union array from nums1 and nums2, and sort it.
• If m + n is odd, index number of union array is median.
• If m + n is even, average of index and index-1 numbers of union array is median.

Results

Runtime: 452 ms, faster than 76.98% of Scala online submissions for Median of Two Sorted Arrays. Memory Usage: 59.2 MB, less than 94.59% of Scala online submissions for Median of Two Sorted Arrays.

Code 2

object Solution {
    def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
        val total = nums1.length + nums2.length
        val index = total/2
        var pre = 0
        var target = 0
        var index1 = -1
        var index2 = -1

        for {
          i <- 0 to targetIndex
        } {
          val (next1, next2) = if(index1 == nums1.length-1) (index1, index2+1) else if(index2 == nums2.length-1) (index1+1, index2) else if(nums1(index1+1) > nums2(index2+1)) (index1, index2+1) else (index1+1, index2)
          if(i == index - 1) pre = if(index1 == next1) nums2(next2) else nums1(next1)
          if(i == index) target = if(index1 == next1) nums2(next2) else nums1(next1)
          index1 = next1
          index2 = next2
        }
        if(total % 2 == 0) (pre + target)/2.0 else target
    }
}

Methods

• Calculate median index from m and n.
• Loop 0 to index
  • Compare each head value of nums1 and nums2
  • Increment index1 if nums1.head is smaller, else increment index2.
  • If i is index - 1, assign current value to pre.
  • If i is index, assign current value to target.
  • update index1 and index2
• If m + n is odd, target is median.
• If m + n is even, average of pre and target is median.

Results

Runtime: 432 ms, faster than 90.48% of Scala online submissions for Median of Two Sorted Arrays. Memory Usage: 59.8 MB, less than 91.89% of Scala online submissions for Median of Two Sorted Arrays.