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

Question

数组“分数”表示参与比赛的每个人的总分。例如：

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 位。等等。

我实际上有一个包含爱丽丝不同“会话”的数组。例如：

[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");

}

我猜“排序”功能和/或使用 indexOf 搜索数组中的元素是问题所在。但是我找不到让这两个操作更高效的方法。

Answer 1

这种方法假设在得分相等的情况下，Alice 应该在得分范围内排在第一位，这意味着如果她得分 90，那么她将排在第 2 位，排在 100 分之后，但高于 90 分的其余部分function calculatePositions(scores, aliceScores) {&nbsp; let positions = [];&nbsp; const uniqueScoresSet = new Set([...scores]);&nbsp; const uniqueScoresArray = Array.from(uniqueScoresSet);aliceScores.forEach((aliceScore) => {&nbsp; &nbsp; let position = uniqueScoresArray.findIndex((score) => aliceScore >= score);&nbsp; &nbsp; position = position === -1 ? scores.length : position + 1;&nbsp; &nbsp; positions.push(position);&nbsp; });&nbsp; return positions;}function main() {&nbsp; const scores = [100, 90, 90, 80, 75, 60];&nbsp; const alice = [50, 65, 77, 90, 102];&nbsp; let result = calculatePositions(scores, alice);&nbsp; console.log(result.join("\n") + "\n");}这种方法假设在得分相同的情况下，Alice 应该排在得分括号的最后，这意味着如果她得分 90，那么她将排在第 4 位，排在 100 分和另外两个 90 分之后。function calculatePositions(scores, aliceScores) {&nbsp; let positions = [];&nbsp; aliceScores.forEach((aliceScore) => {&nbsp; &nbsp; let position = scores.findIndex((score) => aliceScore > score);&nbsp; &nbsp; position = position === -1 ? scores.length : position + 1;&nbsp; &nbsp; positions.push(position);&nbsp; });&nbsp; return positions;}function main() {&nbsp; const scores = [100, 90, 90, 80, 75, 60];&nbsp; const alice = [50, 65, 77, 90, 102];&nbsp; let result = calculatePositions(scores, alice);&nbsp; console.log(result.join("\n") + "\n");}

Answer 2

将您的功能更改getPosition为以下并尝试。刚刚删除了您的排序功能并使用条件进行了完整的数组搜索。const getPosition = (element, scores) => {&nbsp; &nbsp; let length = scores.length;&nbsp; &nbsp; let rank = 1;&nbsp; &nbsp; for(let i=0; i<length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if(scores[i] > element) {&nbsp; &nbsp; &nbsp; &nbsp; rank++;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return rank;}const scores = [100, 90, 90, 80, 75, 60];const alice = [50, 65, 77, 90, 102];console.log(getPosition(77, scores));

Answer 3

这是另一种方法......也许不是最有效的方法，但相信它可以解决问题。这实际上是 Jonas Wilms 对该问题的评论的一种实现。这在某种程度上是一种蛮力解决方案，因为它会遍历 alice 的每个分数的分数数组。一种更有效的方法是将 alice 的分数从高到低排序（但要跟踪原始顺序以便以正确的顺序组织结果），然后同时遍历分数数组和 alice 的数组。请注意，下面的解决方案会运行问题中的测试用例，此外还会针对 1M 分数数组运行测试用例，该数组填充有 99,999 到 0 范围内的随机分数。function climbingLeaderboard(scores, alice) {&nbsp; scores.sort( (a, b) => b - a );&nbsp; aliceRank = [];&nbsp; for ( let aliceScore of alice ) {&nbsp; &nbsp; let scoreIndex = 0;&nbsp; &nbsp; let rank = 0;&nbsp; &nbsp; while ( scoreIndex < scores.length ) {&nbsp; &nbsp; &nbsp; if ( scoreIndex === 0 || scores[ scoreIndex - 1 ] !== scores[ scoreIndex ] ) {&nbsp; &nbsp; &nbsp; &nbsp; rank++;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; if ( scores[ scoreIndex ] <= aliceScore ) {&nbsp; &nbsp; &nbsp; &nbsp; aliceRank.push( rank++ );&nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; scoreIndex++;&nbsp; &nbsp; }&nbsp; &nbsp; if ( scoreIndex === scores.length ) {&nbsp; &nbsp; &nbsp; aliceRank.push( ++rank );&nbsp; &nbsp; }&nbsp; }&nbsp; return aliceRank;}function main() {&nbsp; const scores = [100, 90, 90, 80, 75, 60];&nbsp; const alice = [50, 65, 77, 90, 102];&nbsp; let result = climbingLeaderboard(scores, alice);&nbsp; console.log(result);&nbsp;&nbsp;&nbsp; console.log( 'Generating array of 1M scores' );&nbsp; let scores2 = new Array( 1000000 );&nbsp; for ( let i = 0; i < scores2.length; i++ ) {&nbsp; &nbsp; scores2[ i ] = Math.floor( 100000 * Math.random() );&nbsp; }&nbsp; alice2 = [50000, 65000, 77000, 90000, 102000, -1];&nbsp; let result2 = climbingLeaderboard(scores2, alice2);&nbsp; console.log( `First of the 1M scores is ${scores2[0]} and last score is ${scores2[999999]}` );&nbsp; console.log( result2 );}main();