两个不同大小的排序数组的中位数

Question

我正在为极客http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/从极客那里解决这个问题但是当我实现相同的代码时，那么对于输入A [] = {1,2,3} B [] = {3,6,9,12}它给出了错误的输出作为6，但它应该是3，有人请告诉我我的代码的问题？

//code

#include<iostream>
#include<cmath>

using namespace std;


float single_median(int arr[],int size)//method to find median in an arr

{
    if(size == 0)
    return -1;

    else if(size%2==0)
    return (arr[size/2] + arr[size/2 -1])/2.0;

    else
    return arr[size/2];
}

float medianOf2(int a,int b)//median of two numbers
{
    return ((a+b)/2.0);
}

int medianOf3(int a,int b,int c)//median of 3 numbers
{
    int maximum = max(a,max(b,c));
    int minimum = min(a,min(b,c));
    return ((a+b+c) - maximum - minimum);
}

int medianOf4(int a, int b,int c,int d)//median of 4 numbers
{
    int maximum = max(a,max(b,max(c,d)));
    int minimum = min(a,min(b,min(c,d)));
    return ((a+b+c+d) - maximum - minimum);
}

int find_median(int A[],int m,int B[],int n)
{
    if(m<n)//here we will keep in mind that A is larger than B else we swap
    return find_median(B,n,A,m);

    if(n==0)//if smaller array has no element just find the median of larger array
    return single_median(A,m);

    if(n==1)//if smaller array has one element
    {
        if(m==1)
        return (A[0]+B[0])/2.0;//if both has one element just return the average

        else if(m&1)//when larger array has odd elements
        return medianOf2(medianOf3(B[0],A[m/2 - 1],A[m/2 + 1]),A[m/2]);

        else//for e
        return medianOf3(B[0],A[m/2],A[m/2 -1]);

    }

    if(n==2)
    {
        if(m==2)
        return medianOf4(A[0],B[0],A[1],B[1]);

        else if(m&1)
        return medianOf3(max(B[0],A[m/2 -1]),min(B[1],A[m/2 +1]),A[m/2]);

        else
        return medianOf4(max(B[0],A[m/2 -2]),min(B[1],A[m/2 +1]),A[m/2],A[m/2 -1]);

    }

    int mid_m = (m-1)/2;
    int mid_n = (n-1)/2;

    if(A[mid_m]<B[mid_n])
        find_median(A + mid_m,m/2 +1 ,B,n - mid_n);
    else
        find_median(A,n/2 +1, B + mid_n, n/2 + 1);


}

int main()
{
    int B[] = {1,2,3};
    int A[] = {3,6,9,12};

    cout<<find_median(A,4,B,3);
    return 0;
}

Answer 1

您只是忘记在medianOf4函数中将结果除以2.0，然后返回结果：

int medianOf4(int a, int b,int c,int d)//median of 4 numbers
{
    int maximum = max(a,max(b,max(c,d)));
    int minimum = min(a,min(b,min(c,d)));
    return ((a+b+c+d) - maximum - minimum) / 2.0; # <-- forgot to add "/ 2.0"
}

希望这可以帮助！

Answer 2

public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
    if(nums1== null || nums1.Length<1)
        return result(nums2);
    else if(nums2== null || nums2.Length<1)
        return result(nums1);

    int[] merged = new int[nums1.Length + nums2.Length];
    int num1Ind=0;
    int num2Ind=0;
    int currInd = 0;

    while(num1Ind<nums1.Length &&  num2Ind<nums2.Length){
        if(nums1[num1Ind]< nums2[num2Ind])
            merged[currInd++]=nums1[num1Ind++];
        else
            merged[currInd++]=nums2[num2Ind++];
    }

    if(num2Ind<nums2.Length)
        for(int i=num2Ind; i<nums2.Length; i++)
           merged[currInd++]=nums2[i];
    else if(num1Ind<nums1.Length)
        for(int i=num1Ind; i<nums1.Length; i++)
           merged[currInd++]=nums1[i];

    return result(merged);
}

private double result(int[] merged){
    if(merged.Length==1)
        return merged[0];
     if((merged.Length)%2 !=0)
        return (double)merged[merged.Length/2];
     return (double)(merged[merged.Length/2-1] + merged[merged.Length/2])/2;


}

}