0

ここでは、2 つの並べ替えられた配列の中央値を見つけるためのコードを記述しました。

#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、それらの開始値も含まれています。

左と右のデフォルト値を、MEDIAN-SEARCH(A,B) の呼び出しが以下と同等になるようにします。

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

の不変条件MEDIAN-SEARCH(A,B)は、中央値が常に または のいずれA[left ..right] かにあることBです。Aとがソートされているため、これは最初の呼び出しに当てはまります 。したがって、中央値の定義により、 と の間にBある必要があります 。8 行目と 9 行目の再帰呼び出しにも当てはまります。このアルゴリズムは、median の定義により、配列の一部のうち、median にならない部分のみを除外するためです。中央値が新しい値と値の間にある必要がある場合、2 行目の再帰呼び出しも不変条件を保持します。max(1,ceil(n/2) - m)min(l,ceil(n/2))left > rightBleftright

小さな配列を使って紙の上でアルゴリズムを実行すると、何が起こっているのかがより明確になるはずです。配列が合計 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 のマージ メソッドを使用して、長さが等しくない 2 つの並べ替えられた配列の中央値を見つけるためのコードです。

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 に答える