004 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:
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

详见：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

Java实现：

方法一：常规解法

import java.util.Arrays;

class Solution {

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

        int size1=nums1.length;

        int size2=nums2.length;

        int size=size1+size2;

        int[] nums = new int[size];

        for(int i = 0; i<size1; i++){

            nums[i] = nums1[i];

        }

        for(int i = size1; i<size; i++){

            nums[i] = nums2[i-size1];

        }

        Arrays.sort(nums);

        double median;

        if((size-1)%2 == 0){

            median = nums[(size-1)/2] * 1.0;

        } else {

            median = (nums[(size-1)/2] + nums[((size-1)/2)+1])/2.0;

        }

        return median;

    }

}

　方法二：求第k小的数

public class Solution {

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

        int size1 = nums1.length;

        int size2 = nums2.length;

        int size = size1 + size2;

        if(size % 2 == 1){

            return findKth(nums1, 0, size1, nums2, 0, size2, size / 2 + 1);

        }else{

            return (findKth(nums1, 0, size1, nums2, 0, size2, size / 2) + findKth(nums1, 0, size1, nums2, 0, size2, size / 2 + 1)) /2;

        }

    }

    public double findKth(int[] nums1, int start1, int size1, int[] nums2, int start2, int size2, int k){

        if(size1 - start1 > size2 -start2){

            return findKth(nums2, start2, size2, nums1, start1, size1, k);

        }

        if(size1 - start1 == 0){

            return nums2[k - 1];

        }

        if(k == 1){

            return Math.min(nums1[start1], nums2[start2]); // k==1表示已经找到第k-1小的数，下一个数为两个数组start开始的最小值

        }

        int p1 = start1 + Math.min(size1 - start1, k / 2); // p1和p2记录当前需要比较的那个位

        int p2 = start2 + k - p1 + start1;

        if(nums1[p1 - 1] < nums2[p2 - 1]){

            return findKth(nums1,  p1, size1, nums2, start2, size2, k - p1 + start1);

        }else if(nums1[p1 - 1] > nums2[p2 -1]){

            return findKth(nums1, start1, size1, nums2, p2, size2, k - p2 + start2);

        }else{

            return nums1[p1 - 1];

        }

    }

}

C++实现：

 class Solution {

 public:

     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

         int size1=nums1.size();

         int size2=nums2.size();

         int size=size1+size2;

         if(size&0x1)

             return findKTh(nums1.begin(),size1,nums2.begin(),size2,size/+);

         else

             return (findKTh(nums1.begin(),size1,nums2.begin(),size2,size/)+findKTh(nums1.begin(),size1,nums2.begin(),size2,size/+))/;

     }

     double findKTh(vector<int>::iterator nums1,int m,vector<int>::iterator nums2,int n,int k)

     {

         if(m>n)

             return findKTh(nums2,n,nums1,m,k);

         if(m==)

             return *(nums2+k-);

         if(k==)

             return min(*nums1,*nums2);

         int pa=min(k/,m),pb=k-pa;

         if(*(nums1+pa-)<*(nums2+pb-))

             return findKTh(nums1+pa,m-pa,nums2,n,k-pa);

         else if(*(nums1+pa-)>*(nums2+pb-))

             return findKTh(nums1,m,nums2+pb,n-pb,k-pb);

         else

             return *(nums1+pa-);

     }

 };

参考：

https://www.cnblogs.com/leavescy/p/5877627.html

https://www.cnblogs.com/bakari/p/5082155.html

http://blog.csdn.net/yutianzuijin/article/details/11499917/

巴特西

004 Median of Two Sorted Arrays 两个有序数组的中位数

最新文章

热门文章