0

最適化したいコードに取り組んでいます。このコードは、double 配列を 2 番目の昇順でソートすることに関するものです。最初の入力は整数 N で、2 番目の入力はサイズ N*2 (c と呼びます) の 2D 配列です。次に、配列を の昇順で並べ替えますc[.][1]。2c[i][1]==c[j][1]つの整数iとj、最初の列の要素の昇順でこれらの要素を並べ替えます。したがって、ifのc[i][1]下にあります。例を見てみましょう:c[j][1]c[i][1]<c[j][1]

input 
3
2 3
1 3
4 2

output 
4 2
1 3
2 3

実際のところ、コードは 0.5 秒未満で実行する必要があり、私のコードは本当に遅すぎます。ここにあります

#include <stdio.h>
#include <stdlib.h>

//determining the index of the max elments in an array
int max(int i, int N, int **c)
{
    int j=0;
    int M=0;

    for(j=0;j<i;j++)
    {if(c[j][1]>c[M][1]){M=j;}else{}}
    return M;
}

int main ()
{
    //integers used for the loops
    int i;
    int j;

    //the size of the 2D array is N*2
    int N;
    scanf("%d",&N);
    int **c;
    int mx;
    int maxi;

    //this array is the output, thath is the 2D array sorted
    int e[N][2];

    //2D array we want to sort
    c = malloc(N*sizeof(int*));

    for (i=0;i<N;i++)
    {
        c[i] = malloc(2*sizeof(int));
        for (j=0;j<2;j++)
        {
            scanf("%d",&c[i][j]);
        }
    }

    //at the first step, we have initialized the value of the max
    maxi=max(N,N,c);


    for(i=0;i<N;i++)
    {
        //we sort the c[.][1], and we take the max (called 'mx') of the array. At each step of the loop, we throw away the max from the array c[.][1] (we mean the max found at the precedent step of the loop)

        mx=max(N-i,N,c);

        //Here, we look at the multiple occurence of the max, if there are, we sort the c[.][0] for which c[.][1]=c[mx][1] by ascending order
        if(maxi==mx){int k;
            for(k=0;k <N;k++){if(c[k][1]==c[mx][1]){if(c[k][0]>c[mx][0]){mx=k;}}else{}}
        }else{}

        //we keep the value of the max in order to verify that the same value of the max has another occurence in following steps
        maxi=mx;

        //e is the double array for the output
        e[i][0]=c[mx][0];
        e[i][1]=c[mx][1];
        int j;

        //here we throw away the max from the array
        for(j=mx;j< N-i-1;j++){c[j][1]=c[j+1][1];c[j][0]=c[j+1][0];}
    }

    for(i=0;i<N;i++)
    {printf("%d %d",e[N-1-i][0],e[N-1-i][1]);
        printf("\n");}

}

誰でも助けることができますか？

4

1 に答える 1

0

コードの計算の複雑さが高すぎます。また、はコンパイル時ではなく実行時に決定される変数であるため、int e[N][2]GCC 拡張の下でのみ機能します。 それを改善する簡単な（コーディングの観点から）方法は、C標準ライブラリを利用することです。N
qsort()

struct IntPair
{
    int n[2];
};

int compareIntPair(const void* lhs, const void* rhs)
{
    const struct IntPair *l = (const struct IntPair*)lhs;
    const struct IntPair *r = (const struct IntPair*)rhs;

    if(l->n[1] < r->n[1])
        return -1;
    if(l->n[1] > r->n[1])
        return 1;
    if(l->n[0] < r->n[0])
        return -1;
    if(l->n[0] > r->n[0])
        return 1;
    return 0;
}

int main(void)
{
    //integers used for the loops
    int i;
    //the size of the 2D array is N*2
    int N;
    struct IntPair* c;
    scanf("%d",&N);
    c = (struct IntPair*)calloc(N, sizeof(struct IntPair));

    for(i = 0; i < N; ++i)
    {
        scanf("%d%d", &c[i].n[0], &c[i].n[1]);
    }

    qsort(c, N, sizeof(struct IntPair), compareIntPair);

    for(i = 0; i < N; ++i)
        printf("%d %d\n", c[i].n[0], c[i].n[1]);

    free(c);
    return 0;
}

編集：コメントの質問に答えるには、「N動的割り当ての各要素はサイズ2の1D配列を指すことができますか?」

int compareElem(const void* lhs, const void* rhs)
{
    const int *l = *(const int**)lhs;
    const int *r = *(const int**)rhs;

    if(l[1] < r[1])
        return -1;
    if(l[1] > r[1])
        return 1;
    if(l[0] < r[0])
        return -1;
    if(l[0] > r[0])
        return 1;
    return 0;
}

int main(void)
{
    //integers used for the loops
    int i;
    //the size of the 2D array is N*2
    int N;
    int ** c;
    scanf("%d",&N);
    c = (int**)calloc(N, sizeof(int*));

    for(i = 0; i < N; ++i)
    {
        c[i] = (int*)calloc(2, sizeof(int));
        scanf("%d%d", &c[i][0], &c[i][1]);
    }

    qsort(c, N, sizeof(int*), compareElem);

    for(i = 0; i < N; ++i)
    {
        printf("%d %d\n", c[i][0], c[i][1]);
        free(c[i]);
    }

    free(c);
    return 0;
}
于 2012-08-26T11:31:25.353 に答える