【LeetCode OJ】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)).

解题思路：将两个有序数组合并为一个，设置一个 Map<Integer, Integer>,key值为序号，value值为数值，m+n个数的中位数要分两种情况讨论：

1、m+n为奇数：则(m+n)/2即为其中位数

2、m+n为偶数：则(((m+n)/2-1)+(m+n)/2)/2为中位数

示例代码如下：

public class Solution

{

    public static double findMedianSortedArrays(int[] nums1, int[] nums2)

    {

        int m=nums1.length;

        int n=nums2.length;

        int index; //中位数的位置

        //m+n为奇数

        double result;

        if(m==1&&n==0)

            return nums1[0];

        if(m==0&&n==1)

            return nums2[0];

        Map<Integer, Integer> map=new TreeMap<Integer, Integer>();

        int i=0,j=0,k=0;

        while(i<m&&j<n)

        {

            if(nums1[i]<=nums2[j])

            {

                map.put(k,nums1[i]);

                i++;

                k++;

            }

            else

            {

                map.put(k,nums2[j]);

                j++;

                k++;

            }

        }

        while(i<m)

        {

            map.put(k,nums1[i]);

            i++;

            k++;

        }

        while(j<n)

        {

            map.put(k,nums2[j]);

            k++;

            j++;

        }

        //m+n为奇数

        if((m+n)%2==1)

        {

            result=map.get((m+n)/2);

            return result;

        }

        else

        {

            result=(double)(map.get((m+n)/2-1)+map.get((m+n)/2))/2;

            return result;

        }

    }

}

巴特西

【LeetCode OJ】Median of Two Sorted Arrays

最新文章

热门文章