Median of Two Sorted Arrays

Description

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:

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

The median is 2.0 Example 2:

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

The median is (2 + 3)/2 = 2.5

从两个有序数组中求中位数

Solution

通过数组长度，计算中位数的位置。在两个数组中按大小顺序依次查找，找到中位数所在位置，取出数值计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    totalLen := len(nums1) + len(nums2)

    var p1, p2, index1, index2, sum int

    index1 = int((totalLen - 1) / 2)
    index2 = int(totalLen / 2)

    for i := 0; i < totalLen; i++ {
        if i > index2 {
            break
        }
        var num int
        if p1 < len(nums1) && p2 < len(nums2) {
            if nums1[p1] < nums2[p2] {
                num = nums1[p1]
                p1++
            } else {
                num = nums2[p2]
                p2++
            }
        } else if p1 < len(nums1) {
            num = nums1[p1]
            p1++
        } else {
            num = nums2[p2]
            p2++
        }

        if i == index1 {
            sum += num
        }
        if i == index2 {
            sum += num
        }
    }

    return float64(sum) / 2.0
}