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

Question

数组“分数”表示参与比赛的每个人的总分。例如：User A: 100 pointsUser B: 90 pointsUser C: 90 pointsUser D: 80 pointsUser E: 75 pointsUser F: 60 points根据上面的分数，我们会有这个排名：User A: #1User B: #2  User C: #2User D: #3User E: #4User 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) {

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

}

Answer 2

将您的功能更改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));

Answer 3

这是另一种方法......也许不是最有效的方法，但相信它可以解决问题。这实际上是 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();