爱丽丝(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;
}
我使用此代码
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;
}
}
这很好用