[100天算法】-网易面试题（day 40）

题目描述

有一个班级有 n 个人，给出 n 个元素，第 i 个元素代表 第 i 位同学的考试成绩，接下进行 m 次询问，每次询问给出一个数值 t ，表示第 t 个同学，然后需要我们输出第 t 个同学的成绩超过班级百分之几的人，百分数 p 可以这样算：p = (不超过第 t 个同学分数的人数 ) / n * 100%。输出的时候保留到小数点后 6 位，并且需要四舍五入。
 
输入描述：第一行输入两个数 n 和 m，两个数以空格隔开，表示 n 个同学和 m 次询问。第二行输入 n 个数值 ni，表示每个同学的分数，第三行输入 m 个数值mi，表示每次询问是询问第几个同学。（注意，这里 2<=n，m<=100000，0<=ni<=150，1<=mi<=n）
 
输出描述：输出 m 行，每一行输出一个百分数 p，代表超过班级百分之几的人。
 
示例1：
 
输入 ：
 
3 2
 
50 60 70
 
1 2
 
输出
 
33.333333%
 
66.666667%

方法 1：前缀和

思路

一开始我的思路是，先将 scores 数组排序，这样就能很容易算出 “有多少人不超过当前分数” 这个前缀和。但如果要将 scores 排序的话，还得另外记录 “第 mi 位同学” 排序后是第几位，这样就很麻烦，一点都不优雅。

今天看到 lucifer 的公众号推文后，才发现原来可以把“分数”这个值本身当作数组下标啊，所以思路就变成了：

• 因为分数的范围是 [0, 150]，所以我们可以用一个长度为 150 的数组 prefix 来记录每个分数出现的次数，数组下标是分数值，数组的值就是分数出现的 次数；
• 遍历 scores 数组，对于每个分数 s，prefix[s]++；
• 遍历 prefix，计算前缀和；
• 然后我们就可以实现 $O(1)$ 时间的：
  • 询问第 mi 位同学的分数能超过班上百分之几的人
  • 通过 scores[mi] 找到这位同学的分数 s
  • 通过 prefix[s] 找到不超过分数 s 的人数
  • 算数学吧

复杂度分析

• 时间复杂度：$O(N)$，N 是数组长度。
• 空间复杂度：$O(max(scores))$，前缀和数组，取决于分数范围。

代码

JavaScript Code

/**
 * @param {number[]} scores 全班同学的分数
 * @param {number} mi 第 mi 个同学
 * @return {number} 第 mi 个同学的分数能超过班级百分之几的人
 */
var test = function (scores, mi) {
    // 下标是分数，值是“有多少人是这个分数”
    const prefix = Array(151).fill(0);

    // 先遍历 scores 数组，统计每个分数的人数
    scores.forEach(s => prefix[s]++);

    // 计算前缀和
    // 下标是分数，值是“有多少人不超过这个分数 <=”
    for (let i = 1; i < prefix.length; i++) {
        prefix[i] += prefix[i - 1];
    }

    // 第 mi 个同学的分数
    const score = scores[mi - 1];

    const p = (prefix[score] / scores.length) * 100;
    return p.toFixed(6) + '%';
};

输入输出

const __main__ = function () {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
    });

    console.log('******输入******');
    rl.prompt();
    const inputs = [];
    rl.on('line', line => inputs.push(line));

    rl.on('close', () => {
        const [n, m] = inputs[0].split(' '); // n 个同学， m 次询问
        const scores = inputs[1].split(' ').slice(0, n); // 全班同学的分数
        const asks = inputs[2].split(' ').slice(0, m); // 每次询问的是第几位同学

        console.log('\n******输出******');
        asks.forEach(mi => {
            const p = test(scores, mi);
            console.log(p);
        });
    });
};