做者：帅地
来源：苦逼的码农
今天我要将的那道题是网易 8 月 3 号研发岗笔试的第一题，也是四道题中最简单的一道。那道题涉及到前缀和的利用，所以我想借那道题给各人讲一讲前缀和相关的一些常识，以后各人碰着那道题，就能够快速秒杀了。
问题描述
下面我描述下那道题，不外我给的描述是简化版的，现实上再做笔试题的时候，每道题的描述都巨长，一般城市根据现实场景来给出问题的，有些人可能阅读了十几分钟，然后不晓得本身要干嘛，我那里给出最简化的版本。
有一个班级有 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 250 60 701 2输出33.333333%66.666667%第一题大致是如许，不外不是和原题完全一样哈，在输进和输出有小许区别，因为详细的输进输出我忘了。我那个描述说简化似乎也挺长，不外原题就愈加长了。
解答
那么那道题难吗？说实话不难，不外你能够先本身再脑子里想想怎么做比力好，或许在考场上 20 分钟你还实纷歧定做的出来。
有些人说，那还不简单，每次询问的时候，我都遍历一下所有人的功效，如许的花时间复杂度是 O(n * m)，显然，假设你如许做，那么是必然通不外的，必然会超时。一般暴力法可以通过 20% ~ 30% 的测试用力，假设一道题 20 分的话，能拿到 4~6 分。假设你其实没构想，那么暴力也是个不错的抉择。
1、二分法
那道题我是用二分法做的，就是先对所有人的功效停止排序，不外排序的时候我们需要开一个新的数组来存储。然后每次查询的时候能够通过二分查找停止婚配，因为用到了排序，需要花 O(nlogn) 的时间，m 次查询花的时间大致为 O(mlogn)。所以均匀时间复杂度能够算是 O((m+n)logn)。那个时间复杂度通过所有测试用例，代码如下(没学过java的也能看懂)：
public class Main { // 主函数，相当于c语言的main办法 public static void main(String[] args){ Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); // 存放功效的数组 int[] a = new int[n]; // 存放排序事后的功效 int[] b = new int[n]; // 输进 n 小我的功效 for(int i = 0; i n; i++){ a[i] = in.nextInt(); b[i] = a[i]; } // 排序 Arrays.sort(b); // 停止查询 for(int j = 0; j m; j++){ // 输进是要查询第几个同窗 int t = in.nextInt(); // 把那个同窗的分数拿出来 int fen = a[t - 1]; // 通过二分查找是排在第几位 int sum = binarySearch(b, fen) - 1; double t = sum * 1.0 / n * 100; System.out.printf("%.6f\n", t); } } private static int binarySearch(int[] b, int fen){ int l = 0; int r = b.length - 1; while(l = r){ int mid = l + (r - l) / 2; if(b[mid] fen){ r --; }else if(b[mid] fen){ l++; }else{ // 因为存在分数不异的人，所以还要往后查找 while(mid b.length b[mid] == fen){ mid++; } return mid; } } return 0; }}那里阐明一下，输出的时候我没有输出"%"号哈。前缀和
不外那道题更好的做法是摘用前缀和来做。题设中每个同窗的分数不超越 150，不小于 0，那么我们能够用一个数组 arr，然后让 arr[i] 表达分数不超越 i 的人数。通过那种体例，我们能够把时间复杂度掌握在 O(n+m)。间接看代码吧，会更好理解（那里我就不写输进的代码了，用a[]存放功效，m[]存放m次询问）：
void f(int a[], int m[]){ int n = a.length; int[] arr = new int[151]; //先统计分数为 i 的有几人 for(int i = 0; i n; i++){ arr[a[i]]++; } // 接着构造前缀和 for(int i = 1; i 151; i++){ arr[i] = arr[i] + arr[i-1]; } // 停止 m 次询问 for(int i = 0; i m.length; i++){ // 取出功效 int score = a[m[i]-1]; // 有几人的功效不超越 score的 int sum = arr[score]; System.out.printf("%.6f\n", sum * 1.0 / n * 100 ); }}那种办法就喊做前缀和，用那种办法简单了良多。当然前缀和还有其他利用，例如：
假设给你一个数组 arr[]，然后停止 m 次询问，每次询问输进两个数 i，j（i = j）。要求你输出 arr[i] ~ arr[j] 那个区间的和。那个时候就能够利用前缀和的体例了。前缀和的构造也是很好构造的，例如 arr[] 酿成前缀和的构造体例如下
for(int i = 1; i arr.length; i++){ arr[i] = arr[i] + arr[i-1];}前缀和看起来仍是挺简单的，不外在做题中，或许会有意想不到的感化，例如此次的笔试，所以今天给各人讲解一下。
最初我再问你一个和前缀和类似的问题，给你一串长度为n的数列a1,a2,a3……an，要求对a[i]~a[j]停止m次操做：
操做一：将a[i]~a[j]内的元素都加上P
操做二：将a[i]~a[j]内的元素都减往P
最初再给出一个询问求a[i]-a[j]内的元素之和。
那个你会怎么做呢？那个时候就涉及到差分的常识了，不外它和前缀和类似，感兴致的能够研究一下。
最初
那里关于笔试题有几点定见，因为笔试题大大都都需要我们处置输进输出，而像 leetcode，剑指 offer 都是不需要我们处置那些的，所以会不熟悉，所以我定见能够往刷下往年的实题熟悉一下。
还有就是大部门都是能够间接暴力的，然后能拿 20%~30%的分数，想了非常钟仍是没好的构想的，定见间接暴力。
还有就是有时候笔试是禁绝你用当地 IDE 的，所以我定见日常平凡刷题的时候，间接再网页打代码，别跑到当地 IDE 打好再粘贴过来。