Leetcode - 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 1:

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

The median is 2.0

Merge two arrays into one, and then find the median.

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    all := []int{}
    i := 0
    j := 0
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] < nums2[j] {
            all = append(all, nums1[i])
            i++
        } else {
            all = append(all, nums2[j])
            j++
        }
    }
    for i < len(nums1) {
        all = append(all, nums1[i])
        i++
    }
    for j < len(nums2) {
        all = append(all, nums2[j])
        j++
    }
    var mid float64
    size := len(all)
    if size%2 == 0 {
        mid = (float64(all[size/2-1]) + float64(all[size/2]))/float64(2)
    } else {
        mid = float64(all[size/2])
    }
	return mid
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        int target = total/2;
        int i = 0;
        int j = 0;
        int index = 0;
        int curr = 0;
        while (index <= target) {
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) {
                    curr = nums1[i];
                    i++;                
                } else {
                    curr = nums2[j];
                    j++;                
                }
            } else if (i >= nums1.length && j < nums2.length) {
                curr = nums2[j];
                j++;
            } else if (i < nums1.length && j >= nums2.length) {
                curr = nums1[i];
                i++;
            }
            index++;
            if (total % 2 == 0 && index == target) break;
        }

        if (total % 2 == 1) {
            return curr;
        }
        if (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                return (double)(nums1[i] + curr)/2;
            } else {
                return (double)(nums2[j] + curr)/2;
            }
        }
        if (i >= nums1.length && j < nums2.length) {
            return (double)(nums2[j] + curr)/2;
        }
        return (double)(nums1[i] + curr)/2;
    }
}

• 相关文章
• 全局相关文章