-1

これが中央値選択用の私のバージョンのコードです

#include<iostream>
using namespace std;
#define max 1000
int a[max];
int n;//number of elements
void Swap(int i,int j)
{
    int k=a[i];
    a[i]=a[j];
    a[j]=k;


}
int randint(int l, int u)
{   return l + (RAND_MAX*rand() + rand()) % (u-l+1);
}

void read()
{
    cout<<"  enter number of elements ";
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];

}

void select(int l,int u,int k)
{
    int i,j;
    int t,temp;
    if(l>=u)
         return;
    Swap(l,randint(l,u));
    t=a[l];
    i=l;
    j=u+1;
    for(;;)
    {
        do i++; while(i<=u && a[i]<t);
        do j--;while(a[j]>t);
        if(i>j)
             break;
        temp=a[i];a[i]=a[j];a[j]=temp;
    }
    Swap(i,j);
    if(j<k)
        select(j+1,u,k);
    else if(j>k)
        select(l,j-1,k);



}
int main()
{
    read();
    int l=0;
    int u=n-1;
    int k=int(n/2);
    select(l,u,k);
    if((n&1)==1)
        cout<<a[k]<<endl;
    else
        cout<<(a[k]+a[k-1])/2<<endl;


    return 0;
}

しかし、このコードを実行すると、要素5の入力番号と入力があります

5 3 1 7 2

結果は5です、なぜそれが私に5を表示するのか理解していませんか？私は結果が3でなければならないと思いますか？

4

1 に答える 1

9

手間を最小限に抑えて中央値を計算することに興味がある場合は、線形の複雑さを持つstd::nth_elementを使用することをお勧めします。これは奇数サイズのベクトルの例であり、配列での使用に簡単に適応できますが、コードを適応させてstd::vector：を使用することをお勧めします。

#include <algorithm> // for std::nth_element
#include <vector> // for std::vector

std::vector<int> v = ....;
size_t midIndex = v.size()/2;
std::nth_element(v.begin(), v.begin() + midIndex, v.end());

中央値は

v[midIndex];

これは、偶数サイズのアレイの場合をカバーするように簡単に適合させることもできます。

于 2012-09-03T07:56:59.770 に答える