如何为C中的大量输入(例如200000)优化代码?

问题描述 投票:0回答:1

爱丽丝(Alice)正在玩街机游戏,想爬到排行榜的顶部,并想跟踪自己的排名。该游戏使用了密集排名,因此其排行榜的工作方式如下:

1:得分最高的玩家在排行榜上排名第一。2:分数相同的玩家将获得相同的排名号码,下一位玩家将获得紧随其后的排名号码。

例如,排行榜上的四个玩家得分分别为100、90、90和80。这些玩家的排名分别为1、2、2和3。如果爱丽丝的得分分别是70、80和105,那么她在每局比赛之后的排名分别是第4,第3和第1。

我已经尝试了此代码,该代码可正确处理100000个输入,但是当工作200000个输入时,它将超时。

int* climbingLeaderboard(int scores_count, int* scores, int alice_count, int* alice, int* result_count) 
    {
        //here scores array is sorted in descending order
        //and alice array is sorted in ascending order

        int rank[scores_count];
        int i, j, temp;

        //inserting rank in rank array according to the scores of scores array
        rank[0] = 1;
        temp = scores[0];
        for(i=1;i<scores_count;i++)
        {
            if(scores[i] == temp)
                rank[i] = rank[i-1];
            else
            {
                rank[i] = rank[i-1] + 1;
                temp = scores[i];
            }
        }

        //Now finding the rank of alice's scores and 
        //reusing the alice array to store the required rank

        for(j=0;j<alice_count;j++)
        {
            //case 1: if alice's score is the lower 
            //than the lowest score of scores array
            if(alice[j] < scores[scores_count-1])
                alice[j] = rank[scores_count-1] + 1;

            //case 2: if alice's score is greater 
            //than the highest score pf the scores array
            else if(alice[j] > scores[0])
                alice[j] = 1;

            //case 3: when alice's score is in between the max-min range    
            else
            {
                for(i=0;i<scores_count;i++)
                {
                    if((alice[j] > scores[i]) || (alice[j]) == scores[i])
                    {
                        alice[j] = rank[i];
                        scores_count = i;
                        break;
                    }
                }
            }

        }

        *result_count = alice_count;

        return alice;
    }
c optimization timing
1个回答
0
投票

我使用此代码

int binarySearchModified(int low, int up, int data, int *ar)
{
    int mid;
    while (up >= low) 
    {
        mid = (low + up)/2;
        if(ar[mid] == data)
            return mid;
        if(ar[mid] > data)
            low = mid + 1;
        if(ar[mid] < data)
            up = mid - 1;
    }

    return low;
}

而不是

for(i=0;i<scores_count;i++)
{
    if((alice[j] > scores[i]) || (alice[j]) == scores[i])
    {
         alice[j] = rank[i];
         scores_count = i;
         break;
     }
 }

这很好用

© www.soinside.com 2019 - 2024. All rights reserved.