排名数组元素

Question

我需要一种算法来在 Javascript 中对数组元素进行排序。

例如：我有一个如下的数组：

[79, 5, 18, 5, 32, 1, 16, 1, 82, 13]

我需要按值对条目进行排名。因此，82 应该获得排名 1，79 排名 2，以此类推。 如果两个条目具有相同的值，则它们会获得相同的排名，并且较低值的排名会上升。

所以对于这个数组，新的排名数组将是：

[2, 7, 4, 7, 3, 9, 5, 9, 1, 6] 

我该怎么做？

- Yùz Nagami

---

数组中的数字总是唯一的吗？编辑：根据示例显然不是。 - Matt Cain

这个模式没有意义。你能提供更好的问题描述吗？ - pp19dd

它们在问题中显然不是唯一的，有2个5和2个1。 - Ben McCormick

你在发问之前有尝试过吗？ - Syjin

看起来像是作业。 - user757095

重要的是排名处理重复条目，否则只是排序。如果这是作业@CrisimIlNumenoreano，那么这是相当简单的作业。 - Chris Nadovich

Answer 1

var arr = [79, 5, 18, 5, 32, 1, 16, 1, 82, 13];
var sorted = arr.slice().sort(function(a,b){return b-a})
var ranks = arr.map(function(v){ return sorted.indexOf(v)+1 });
console.log(ranks);

结果：

[2, 7, 4, 7, 3, 9, 5, 9, 1, 6]

如果你想要与旧版浏览器兼容，你可能需要为indexOf定义一个shim和map（请注意，如果你想要在非常大的数组上快速执行此操作，最好使用for循环，并使用对象作为映射而不是indexOf）。

- Denys Séguret

---

看起来你们没有读清楚问题。似乎原帖需要获取一个排名数组。 - VisioN

那个老掉牙的问题——错误的排序^^ .sort(function(a,b){return a-b}) - Christoph

地图可能也需要进行shimmed（IE-9）。但是解决方案真的很好！ - Christoph

多个重复条目时，这确实能正常工作吗？ - Chris Nadovich

不适用于包含重复值的数组。它会跳过排名。 - Abdullah Aman

Answer 2

由于使用了ECMAScript 5功能，旧浏览器不支持此功能，但它允许您快速简洁地生成大型数组的排名。 （它不使用线性搜索的indexOf，因此对于大型数组可能会很慢。）

function cmp_rnum(a,b) {
    // comparison function: reverse numeric order
    return b-a;
}
function index_map(acc, item, index) {
    // reduction function to produce a map of array items to their index
    acc[item] = index;
    return acc;
}
function ranks(v) {
    var rankindex = v.slice().sort(cmp_rnum).reduceLeft(index_map, Object.create(null));
    // reduceLeft() is used so the lowest rank wins if there are duplicates
    // use reduce() if you want the highest rank
    return v.map(function(item){ return rankindex[item]+1; });
}

示例输出：

> ranks([79, 5, 18, 5, 32, 1, 16, 1, 82, 13]);
  [2, 7, 4, 7, 3, 9, 5, 9, 1, 6]

- Francis Avila

---

我必须使用 reduceRight。 - timhc22

这真的是正确的结果吗？有8个唯一的值。怎么会有第9名的排名呢？没有东西排在第8位。我不认为这个解决方案有效，但我没有声望来投票反对它。 - Chris Nadovich

@ChrisNadovich的结果与原帖要求的结果和被接受的答案的结果完全相同。原帖作者表示：“如果两个条目具有相同的值，则它们将获得相同的排名，并且较低值的排名将提高。”因此，8被提升到了9。 - Francis Avila

好的，@FrancisAvila，我承认错误。我想我被自己的要求蒙住了眼睛，即当存在并列时，仅对唯一值进行排名。 - Chris Nadovich

uncaught TypeError: reduceLeft is not a function. It looks like this should be reduce - BurnsBA

Answer 3

function rank(arr, f) {
    return arr
    .map((x, i) => [x, i])
    .sort((a, b) => f(a[0], b[0]))
    .reduce((a, x, i, s) => (a[x[1]] =
        i > 0 && f(s[i - 1][0], x[0]) === 0 ? a[s[i - 1][1]] : i + 1, a), []);
}

使用方法：

rank([79, 5, 18, 5, 32, 1, 16, 1, 82, 13], (a, b) => b - a);
// [2, 7, 4, 7, 3, 9, 5, 9, 1, 6] 

看起来有点丑，但它不使用indexOf()或对象/映射，所以它不仅运行速度更快，更重要的是，它尊重由比较函数定义的“同级性”意义。如果使用indexOf()或对象，则“同级性”只能意味着a === b或String(a) === String(b)。

或者，可以使用findIndex()：

function rank(arr, f) {
    const sorted = arr.slice().sort(f)
    return arr.map(x => sorted.findIndex(s => f(x, s) === 0) + 1)
}

- user5949942

---

rankNumbers([2, 5, 5, 10, 8], (a, b) => a - b) 返回 [1, 2, 2, 5, 4]，即跳过了排名为 3 的数字。我知道重复的数字会被赋予相同的排名，但跳过排名为 3 是否合理呢？也许是；很想听听您的判断。 - Tom

你认为它们都应该有排名(2 + 3) / 2 = 2.5，因为它们共享排名2和排名3，这样说不好吗？ - Tom

我同意你的看法，@Tom。上述算法似乎不正确，它们跳过了排名值。 - Chris Nadovich

@ChrisNadovich 请点击此处查看比赛排名。https://en.wikipedia.org/wiki/Ranking。相同比较的项目将获得相同的排名编号，然后在排名编号中留下间隔。这是比赛中的标准做法。 - undefined

@Mohsen Alyafei毫无疑问，你所说的是真的。然而，我并不是在寻找那种排名。 - undefined

Answer 4

JavaScript ES6简单的两行解决方案。

var arrayRankTransform = arr => {
  const sorted = [...arr].sort((a, b) => b - a);
  return arr.map((x) => sorted.indexOf(x) + 1);
};

console.log(arrayRankTransform([79, 5, 18, 5, 32, 1, 16, 1, 82, 13]));

- Penny Liu

Answer 5

我不擅长JavaScript，但在PHP中可以很容易地完成以下操作。熟悉JavaScript的人可以提供相关代码。

$marks = [79, 5, 18, 5, 32, 1, 16, 1, 82, 13];

public function getRank($marks) {
    $rank = 1; $count = 0; $ranks = [];
    //sort the marks in the descending order
    arsort($marks,1);
    foreach($marks as $mark) {
      //check if this mark is already ranked
      if(array_key_exists($mark, $ranks)) {
       //increase the count to keep how many times each value is repeated
       $count++;
       //no need to give rank - as it is already given
      } else {
        $ranks[$mark] = $i+$j;
        $i++;
      }
    return $ranks;
}

- Suresh Bala

---

我不知道为什么这个被投票否决了。它有一些问题，但似乎是唯一可适应成正确解决方案的方法。只需摆脱 +$j 和 $count。$i 仅递增唯一值。 - Chris Nadovich

Answer 6

我在编写一个操作调度脚本时需要同样的代码段。我使用了对象及其属性/键，它们可以拥有任何值并且可以随时访问。另外，根据我在一些文章中读到的，对象属性的搜索可能比数组搜索更快。

下面的脚本有三个简单的步骤：

1. 对值进行排序（升序或降序不会影响脚本的其余部分）

2. 查找每个值的排名和出现次数

3. 使用步骤 2 的数据用排名替换给定的值

注意！下面的脚本将不会输出重复的排名，而是为重复的值/元素递增排名。

function rankArrayElements( toBeRanked ) {

// STEP 1
var toBeRankedSorted = toBeRanked.slice().sort( function( a,b ) { return b-a; } ); // sort descending
//var toBeRankedSorted = toBeRanked.slice().sort( function( a,b ) { return a-b; } ); // sort ascending

var ranks = {}; // each value from the input array will become a key here and have a rank assigned
var ranksCount = {}; // each value from the input array will become a key here and will count number of same elements

// STEP 2
for (var i = 0; i < toBeRankedSorted.length; i++) { // here we populate ranks and ranksCount
    var currentValue = toBeRankedSorted[ i ].toString();

    if ( toBeRankedSorted[ i ] != toBeRankedSorted[ i-1 ] ) ranks[ currentValue ] = i; // if the current value is the same as the previous one, then do not overwrite the rank that was originally assigned (in this way each unique value will have the lowest rank)
    if ( ranksCount[ currentValue ] == undefined ) ranksCount[ currentValue ] = 1; // if this is the first time we iterate this value, then set count to 1
    else ranksCount[ currentValue ]++; // else increment by one
}

var ranked = [];

// STEP 3
for (var i = toBeRanked.length - 1; i >= 0; i--) { // we need to iterate backwards because ranksCount starts with maximum values and decreases
    var currentValue = toBeRanked[i].toString();

    ranksCount[ currentValue ]--;
    if ( ranksCount[ currentValue ] < 0 ) { // a check just in case but in theory it should never fail
        console.error( "Negative rank count has been found which means something went wrong :(" );
        return false;
    }
    ranked[ i ] = ranks[ currentValue ]; // start with the lowest rank for that value...
    ranked[ i ] += ranksCount[ currentValue ]; // ...and then add the remaining number of duplicate values
}

return ranked;}

我还需要为我的脚本做一些其他的事情。

上面的输出具有以下含义：

• 索引 - 输入数组中元素的ID

• 值 - 输入数组中元素的排名

我需要基本上“交换索引和值”，这样我就有了一个元素ID列表，按照它们的排名顺序排列：

function convertRanksToListOfElementIDs( ranked ) {  // elements with lower ranks will be first in the list

var list = [];

for (var rank = 0; rank < ranked.length; rank++) { // for each rank...
    var rankFound = false;
    for (var elementID = 0; elementID < ranked.length; elementID++) { // ...iterate the array...
        if ( ranked[ elementID ] == rank ) { // ...and find the rank
            if ( rankFound ) console.error( "Duplicate ranks found, rank = " + rank + ", elementID = " + elementID );
            list[ rank ] = elementID;
            rankFound = true;
        }
    }
    if ( !rankFound ) console.error( "No rank found in ranked, rank = " + rank );
}

return list;}

以下是一些示例：

ToBeRanked:

[36, 33, 6, 26, 6, 9, 27, 26, 19, 9]

[12, 12, 19, 22, 13, 13, 7, 6, 13, 5]

[30, 23, 10, 26, 18, 17, 20, 23, 18, 10]

[7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

[7, 7, 7, 7, 7, 2, 2, 2, 2, 2]

[2, 2, 2, 2, 2, 7, 7, 7, 7, 7]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

rankArrayElements( ToBeRanked ):

[0, 1, 8, 3, 9, 6, 2, 4, 5, 7]

[5, 6, 1, 0, 2, 3, 7, 8, 4, 9]

[0, 2, 8, 1, 5, 7, 4, 3, 6, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[5, 6, 7, 8, 9, 0, 1, 2, 3, 4]

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

将排名数组元素转换为元素ID列表( convertRanksToListOfElementIDs( rankArrayElements( ToBeRanked ) ) ):

[0, 1, 6, 3, 7, 8, 5, 9, 2, 4]

[3, 2, 4, 5, 8, 0, 1, 6, 7, 9]

[0, 3, 1, 7, 6, 4, 8, 5, 2, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[5, 6, 7, 8, 9, 0, 1, 2, 3, 4]

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

- svinec

Answer 7

我创建了Rank_JS Pro。

<script>https://cdn.statically.io/gl/maurygta2/mquery/master/Rank Tools/rank.js</script>

基础方法：

var a = {
  b: 2,
  c: 7
}
Rank_Tools.rank(a,(pos,name,value) => {
  return pos + ". "+name+" "+value;
})
// result
// rank1 = 1. c 7
// rank 2 = 2. b 2

- Anitta Developer

Answer 8

这种替代方式不需要输入数组排序：

// O(n^2)
const rank = (arr) => {
  // Create a temporary array to keep metadata 
  // regarding each entry of the original array
  const tmpArr = arr.map(v => ({
    value: v,
    rank: 1,
  }));

  // Get rid of douplicate values
  const unique = new Set(arr);

  // Loops through the set
  for (let a of unique) {
    for (let b of tmpArr) {
      // increment the order of an element if a larger element is pressent
      if (b.value < a) {
        b.rank += 1;
      }
    }
  }

  // Strip out the unnecessary metadata 
  return tmpArr.map(v => v.rank);
};

console.log(rank([2600, 200, 36, 36, 400, 2, 0, 0]));
// => [1, 3, 4, 4, 2, 5, 6, 6]

console.log(rank([79, 5, 18, 5, 32, 1, 16, 1, 82, 13]));
// => [2, 7, 4, 7, 3, 8, 5, 8, 1, 6]

- Olian04

Answer 9

在我看来，这里有几个解决方案是不正确的，因为它们没有正确处理在重复值之后出现的值。这些跟随者应该获得下一个排名。最高排名应等于数组中唯一值的数量。这个解决方案（使用PHP）在我看来是正确的。基本上是@Suresh的解决方案，但已经修复了错误。

  function rank($marks){
    $rank = 1; $ranks = [];
    rsort($marks,SORT_NUMERIC);
    foreach($marks as $mark) {
      if(!isset($ranks[$mark])) {
        $ranks[$mark] = $rank++;
      }
    }
    return $ranks;
   }

- Chris Nadovich

Answer 10

这应该可以处理数组中的重复键

function rank(arry) {
    let sorted = arry.slice().sort(function (a, b) {
        return b - a
    });


    let currentRank = sorted.length;
    let rankValue = null;
    let ranks = [];

    sorted.forEach(value => {
        if(value !== rankValue && rankValue !==null) {
            currentRank--;
        }

        ranks.push({value,currentRank});
        rankValue = value;
    });

    let mapRanksToArrayValues = arry.map(function (x) {
        let _rank = null;
        ranks.forEach( rank => {
            if(rank.value === x ) {
                _rank =  rank.currentRank;
                return;
            }
        });
        return _rank;
    });

    return mapRanksToArrayValues;
}

- Abdullah Aman