如何在 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 位。等等。
我实际上有一个包含爱丽丝不同“会话”的数组。例如：
[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 搜索数组中的元素是问题所在。但是我找不到让这两个操作更高效的方法。
手掌心3回答
-
浮云间
这种方法假设在得分相等的情况下，Alice 应该在得分范围内排在第一位，这意味着如果她得分 90，那么她将排在第 2 位，排在 100 分之后，但高于 90 分的其余部分function calculatePositions(scores, aliceScores) { let positions = []; const uniqueScoresSet = new Set([...scores]); const uniqueScoresArray = Array.from(uniqueScoresSet);aliceScores.forEach((aliceScore) => { let position = uniqueScoresArray.findIndex((score) => aliceScore >= score); position = position === -1 ? scores.length : position + 1; positions.push(position); }); return positions;}function main() { const scores = [100, 90, 90, 80, 75, 60]; const alice = [50, 65, 77, 90, 102]; let result = calculatePositions(scores, alice); console.log(result.join("\n") + "\n");}这种方法假设在得分相同的情况下，Alice 应该排在得分括号的最后，这意味着如果她得分 90，那么她将排在第 4 位，排在 100 分和另外两个 90 分之后。function calculatePositions(scores, aliceScores) { let positions = []; aliceScores.forEach((aliceScore) => { let position = scores.findIndex((score) => aliceScore > score); position = position === -1 ? scores.length : position + 1; positions.push(position); }); return positions;}function main() { const scores = [100, 90, 90, 80, 75, 60]; const alice = [50, 65, 77, 90, 102]; let result = calculatePositions(scores, alice); console.log(result.join("\n") + "\n");} -
狐的传说
将您的功能更改getPosition为以下并尝试。刚刚删除了您的排序功能并使用条件进行了完整的数组搜索。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)); -
郎朗坤
这是另一种方法......也许不是最有效的方法，但相信它可以解决问题。这实际上是 Jonas Wilms 对该问题的评论的一种实现。这在某种程度上是一种蛮力解决方案，因为它会遍历 alice 的每个分数的分数数组。一种更有效的方法是将 alice 的分数从高到低排序（但要跟踪原始顺序以便以正确的顺序组织结果），然后同时遍历分数数组和 alice 的数组。请注意，下面的解决方案会运行问题中的测试用例，此外还会针对 1M 分数数组运行测试用例，该数组填充有 99,999 到 0 范围内的随机分数。function climbingLeaderboard(scores, alice) { scores.sort( (a, b) => b - a ); aliceRank = []; for ( let aliceScore of alice ) { let scoreIndex = 0; let rank = 0; while ( scoreIndex < scores.length ) { if ( scoreIndex === 0 || scores[ scoreIndex - 1 ] !== scores[ scoreIndex ] ) { rank++; } if ( scores[ scoreIndex ] <= aliceScore ) { aliceRank.push( rank++ ); break; } scoreIndex++; } if ( scoreIndex === scores.length ) { aliceRank.push( ++rank ); } } return aliceRank;}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); console.log( 'Generating array of 1M scores' ); let scores2 = new Array( 1000000 ); for ( let i = 0; i < scores2.length; i++ ) { scores2[ i ] = Math.floor( 100000 * Math.random() ); } alice2 = [50000, 65000, 77000, 90000, 102000, -1]; let result2 = climbingLeaderboard(scores2, alice2); console.log( `First of the 1M scores is ${scores2[0]} and last score is ${scores2[999999]}` ); console.log( result2 );}main();
随时随地看视频慕课网APP
相关分类
JavaScript