0

在这里，我编写了用于查找两个排序数组的中位数的代码：

#include<iostream>
using namespace std;
#define L  5
#define  M 6
 const int N=L+M;
int A[1000];//define 1 indexed aarray
int B[1000];
int max(int c,int d){
    return (c>=d)?c:d;

}
int min(int c,int d)
{
    return (c<=d)?c:d;
}

void  read(){
    cout<<" enter A array "<<endl;
    for (int i=1;i<=L;i++)
        cin>>A[i];
    cout<<endl;
    cout<<"enter B array  "<<endl;
    for (int i=1;i<=M;i++)
        cin>>B[i];
    cout<<endl;


}
int median(int a[],int b[],int left,int right){
    if (left>right) {
        return median(b,a,max(1,(N/2)-L),min(M,N/2));
    }
    int i=int(left+right)/2;
    int j=int(N/2)+i;
    if((j==0 || a[i]>b[j]) && (j==M || a[i]<=b[j+1])){
        return a[i];
    }
    else
    {
        if((j==0 || a[i]>b[j])  &&(j!=M && a[i]>b[j+1]))
        return median(a,b,left,i-1);
    }


        return median(a,b,i+1,right);

}

int main(){




    return 0;
}

我的问题是什么是左右值？从介绍到算法，我只是不明白左右变量的值是什么？我已将 left 和 right 定义为 1 和 N 并使用以下数组进行测试：

3 5 7 9 11 13
1 2 4 8 10

答案是 13，这是不正确的肯定，什么是错的？

4

3 回答 3

3

您在评论中引用的作业问题看起来很好地解释了left和right，包括它们的起始值：

让 left 和 right 的默认值使得调用 MEDIAN-SEARCH(A,B) 等效于

MEDIAN-SEARCH(A[1 ..l],B[1 ..m],max(1,ceil(n/2) - m),min(l,ceil(n/2)))

in 的不变量MEDIAN-SEARCH(A,B)是中位数总是在A[left ..right] 或B中。这对于初始调用是正确的，因为 A和B已排序，因此根据中位数的定义，它必须介于 max(1,ceil(n/2) - m)和之间min(l,ceil(n/2))，包括在内。第 8 行和第 9 行的递归调用也是如此，因为该算法仅消除了数组中不能为中值定义的中值的部分。第 2 行的递归调用也保留了不变量，因为如果left > right中位数必须在B新值left和right值之间。

如果你在纸上用小数组完成算法，应该会更清楚发生了什么。如果您的数组小于总共 16 个元素，则该算法只需几个步骤即可收敛，因此它在纸上应该是相当可行的。

于 2012-03-13T15:12:37.503 回答
2

请考虑以下

std::cout << "enter all number separated by a space ending with 'q'" 
          << std::endl;
std::vector<int> v(
    (std::istream_iterator<int>(std::cin)),
     std::istream_iterator<int>());

std::sort(v.begin(), v.end());
std::cout << "median value is: " 
          << std::advance(v.begin(), v.size()/2); 
          << std::endl;
于 2012-03-13T14:39:15.887 回答
0

这是使用mergesort的merge方法找到两个长度不等的排序数组的中位数的代码

package FindMedianBetween2SortedArrays;

import java.util.Scanner;

public class UsingMergeMethodOfMergeSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        try{
            System.out.println("Enter the number of elements in the first SORTED array");
            int n = in.nextInt();
            int[] array1 = new int[n];
            System.out.println("Enter the elements of the first SORTED array");
            for(int i=0;i<n;i++)
                array1[i]=in.nextInt();
            System.out.println("Enter the number of elements in the second SORTED array");
            int m = in.nextInt();
            int[] array2 = new int[m];
            System.out.println("Enter the elements of the second SORTED array");
            for(int i=0;i<m;i++)
                array2[i]=in.nextInt();
            System.out.println("Median of the two SORTED arrays is: "+findMedianUsingMergeOfMergeSort(array1,array2));
        }
        finally{
            in.close();
        }
    }
    private static int findMedianUsingMergeOfMergeSort(int[] a, int[] b) {

    /*  a1 array and a2 array can be of different lengths.
        For Example:
      1.
        a1.length = 3
        a2.length = 6
        totalElements = 3+6=9 (odd number)
      2.
        a1.length = 4
        a2.length = 4
        totalElements = 4+4=8 (even number)
    */
        int totalElements = a.length+b.length;  // totalElements is the addition of the individual array lengths
        int currentMedian = 0;
        int prevMedian = 0;
        int i=0; // Index for traversing array1
        int j=0; // Index for traversing array2
        for(int k=0;k<totalElements;k++){    // k is index for traversing the totalElements of array1 and array2


        /*NOTE: In this entire for loop, the "if", "else" and "else if" is VERY IMP. DONOT interchange among them*/

            // if array1 is exhausted
            if(i==a.length)
                currentMedian=b[j++]; // elements of the second array would be considered


            // if array2 is exhausted
            else if(j==b.length)
                currentMedian=a[i++]; // elements of the first array would be considered

            else if(a[i]<b[j])
                currentMedian=a[i++];

            else //(b[j]<=a[i])            // this condition is ONLY "else" and not "if" OR "else if"
                currentMedian=b[j++];

            if(k==totalElements/2) // we reached the middle of the totalElements where the median of the combined arrays is found
                break;                 

            prevMedian = currentMedian;

        }

        // if the totalElements are odd
        if(totalElements%2!=0)
            return currentMedian;
        else
            return (prevMedian+currentMedian)/2;
    }
}
/*
Analysis:
    Time Complexity = Linear Time, O((m+n)/2)
    Space Complexity = O(1)
*/
于 2015-01-12T06:10:43.670 回答