0

この問題のコードを書きました：

負でない整数のリストが与えられた場合、それらが最大数になるように並べ替えます。

たとえば、[3, 30, 34, 5, 9] の場合、形成される最大の数値は 9534330 です。

注: 結果は非常に大きくなる可能性があるため、整数ではなく文字列を返す必要があります。

基本的にこのコードで達成しようとしているのは、最初に最上位桁で基数ソートロジックを使用し、それを降順で配置することです。後で私は2番目の最上位桁などをやっています。ペアのベクトルを渡すことで関数を使用std::sort()しました。ペアの最初が値で、ペアの 2 番目がインデックスです。以下は私のコードです：

bool radixOrder(pair<int,int> p1, pair<int,int> p2)
{
    int val1=p1.first;
    int e1=p1.second;
    int val2=p2.first;
    int e2=p2.second;
    if(val1==val2 && e1==e2)
    {
        return val1==val2;
    }
    else if(((val1/e1)%10) == ((val2/e2)%10))
    {
        while(val1/e1 == val2/e2)
        {
            if(e1/10!=0)
                e1=e1/10;
            if(e2/10!=0)
                e2=e2/10;
        }
        return (val1/e1)%10 > (val2/e2)%10;
    }
    else
    {
        return (val1/e1)%10 > (val2/e2)%10;
    }
}

vector<pair<int,int> > createVNew(vector<int>& v)
{
    vector<pair<int,int> > temp;
    for(int i=0; i<v.size(); i++)
    {
        cout << i << endl;
        int val=v[i], e=1;
        if(v[i]==0)
        {
            temp.push_back(make_pair(val, 1));
        }
        else
        {
            while((e/v[i])==0)
                e*=10;
            if(e!=v[i])
            {
                temp.push_back(make_pair(val,e/10));
            }
            else if(e==v[i])
            {
                temp.push_back(make_pair(val,e));
            }
        }
    }
    return temp;
}

string largestNumber(vector<int>& v)
{
    int e=1;
    vector< pair<int,int> > vnew=createVNew(v);
    sort(vnew.begin(), vnew.end(), radixOrder);
    stringstream s;
    for(int i=0; i<vnew.size(); i++)
    {
        s<<vnew[i].first;
    }
    return s.str();
}

largestNumber(..)目的の文字列を返す私の関数です。今、このコードは、私が試すことができるゼロ以外のほとんどの入力に対して正常に機能します。しかし、入力が 0 の長いベクトルの場合は、次のようになります。

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ]

浮動小数点例外が発生しています。

解決策を見つけようとしましたが、できませんでした。私は cpp の初心者です。

4

1 に答える 1

3

関数が要件radixSort、つまり非反射性に違反しています(つまり、返さなければならないが、実行が最初の分岐に行くため返されます)。CompareradixOrder(x, x)falsetrueif

したがって、未定義の動作の典型的な例がここにあります。コードの一部を次のように書き直す必要があると思います

if (e1==e2)
{
    return val1 > val2;
}

ただし、入力数値を文字列として逆順にソートするだけで問題を解決できます。

于 2015-06-15T09:15:55.843 に答える