JS 笔试题——相对名次

给你一个长度为 的整数数组 ，其中 是第 位运动员在比赛中的得分。所有得分都互不相同 。

运动员将根据得分 决定名次 ，其中名次第 的运动员得分最高，名次第 的运动员得分第 高，依此类推。运动员的名次决定了他们的获奖情况：

• 名次第 的运动员获金牌 。
• 名次第 的运动员获银牌 。
• 名次第 的运动员获铜牌 。
• 从名次第 到第 的运动员，只能获得他们的名次编号（即，名次第 的运动员获得编号 ）。

使用长度为 的数组 返回获奖，其中 是第 位运动员的获奖情况。

示例 1：

输入：score = $[5,4,3,2,1]
输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]

示例 2：

输入：score = [10,3,8,9,4]
输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"]

分析：

1. 分数数组需要降序排列，这里实现插入排序法和快速排序法两种。
2. 遍历分数数组中每一个分数对应的名次。
3. 如果是前三，则返回，，。其他返回序号即可。

完整代码：

/**
 * @param {number[]} score
 * @return {string[]}
 */
var findRelativeRanks = function(score) {
    let name = ["Gold Medal","Silver Medal","Bronze Medal"];
    let arr = score.concat([]);
    quickSort(arr); // 这里也可以使用 insertSort
    let ans = [];
    for (let i = 0; i < score.length; i++) {
        let idx = arr.indexOf(score[i]);
        if (idx < 3) {
            ans.push(name[idx]);
        } else {
            ans.push(idx + 1 + '');
        }
    }
    return ans;
};

var insertSort = function (arr) {
    let j;
    for (let i = 1; i < arr.length; i++) {
        let cur = arr[i];
        for (j = i; j > 0; j--) {
            if (arr[j - 1] < cur) {
                arr[j] = arr[j - 1];
            } else {
                break;
            }
        }
        arr[j] = cur;
    }
}

var quickSort = function (arr) {
    let sort = ((arr, left, right) => {
        let p = Math.floor((left + right) / 2);
        let pivot = arr[p];
        let i = left, j = right;
        while (i < j) {
            for (; !(i >= p || arr[i] < pivot); i++) {}
            if (i < p) {
                arr[p] = arr[i];
                p = i;
            }

            for (; !(j <= p || arr[j] > pivot); j--) {}
            if (p < j) {
                arr[p] = arr[j];
                p = j;
            }
        }
        arr[p] = pivot;

        if (p - left > 1) {
            sort(arr, left, p - 1);
        }
        if (right - p > 1) {
            sort(arr, p + 1, right);
        }
    });
    sort(arr, 0, arr.length);
}