506. 相对名次

题目

给出  N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。

(注：分数越高的选手，排名越靠前。)

例

输入: [5, 4, 3, 2, 1] 输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] 解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal"). 余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。

题解

希尔排序

/**
 * @param {number[]} score
 * @return {string[]}
 */
var findRelativeRanks = function(score) {
  let t = [...score];
  shellSort(t);

  let res = [];

  for (let s of score) {
    if (t.indexOf(s) === 0) res.push("Gold Medal");
    else if (t.indexOf(s) === 1) res.push("Silver Medal");
    else if (t.indexOf(s) === 2) res.push("Bronze Medal");
    else res.push(t.indexOf(s) + 1 + "");
  }
  return res;
};

function shellSort(arr) {
  for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
    // 分组
    for (let i = gap; i < arr.length; ++i) {
      let cur = arr[i];
      let preIndex = i - gap;
      while (preIndex >= 0 && cur > arr[preIndex]) {
        arr[preIndex + gap] = arr[preIndex];
        preIndex -= gap;
      }
      arr[preIndex + gap] = cur;
    }
  }
}