提问者:小点点

如何在javascript大集合中进行排序和搜索


数组“分数”表示参加比赛的每个人的总分。 所以举个例子:

User A: 100 points
User B: 90 points
User C: 90 points
User D: 80 points
User E: 75 points
User F: 60 points

根据以上得分,我们将得到以下排名:

User A: #1
User B: #2  
User C: #2
User D: #3
User E: #4
User F: #5

这种排序法沿用了密集排序法。

那么我们就有一个名为Alice的用户。 如果她得到55分,她将排在#6的位置(根据上面的排名)。 如果她得了90分,她将排在第2位。 等等。

我实际上有一个数组,其中包含Alice的不同“会话”。 因此具有例如:
[55,90]

这意味着爱丽丝第一次将被排在第6位。 而她将第二次排在第二位。

我把它编好了,它能用。 然而,这似乎并不是很有效率。 对于大型数据集,分数数组中有50万个条目,它将超时。 这是代码:

const getPosition = (element, scores) => {
    scores.push(element);
    scores.sort(function (a,b) { return b-a; });
    return scores.indexOf(element)+1;
}

function climbingLeaderboard(scores, alice) {
    var uniqueSet = new Set(scores);
    scores = [...uniqueSet];
    var positions = [];
    let aliceIndex = 0;
    while(aliceIndex < alice.length){
        positions.push(getPosition(alice[aliceIndex], scores));
        aliceIndex++;
    }
    return positions;
}

function main() {
    const scores = [100, 90, 90, 80, 75, 60];
    const alice = [50, 65, 77, 90, 102];
    let result = climbingLeaderboard(scores, alice);
    console.log(result.join("\n") + "\n");
}

我猜“sort”-函数和/或用indexOf在数组中搜索元素是问题所在。 但我找不到一个方法来使这两个行动更有效率。


共1个答案

匿名用户

GetPosition函数更改为下面,然后尝试。 只是删除了排序函数,并用一个条件进行全数组搜索。

null

const getPosition = (element, scores) => {
    let length = scores.length;
    let rank = 1;
    for(let i=0; i<length; i++) {
        if(scores[i] > element) {
        rank++;
      }
    }
    return rank;
}
const scores = [100, 90, 90, 80, 75, 60];
const alice = [50, 65, 77, 90, 102];

console.log(getPosition(77, scores));