今天我要将的这道题是网易 8 月 3 号研发岗笔试的第一题,也是四道题中最简单的一道 。这道题涉及到前缀和的应用,所以我想借这道题给大家讲一讲前缀和相关的一些知识,以后大家遇到这道题,就可以快速秒杀了 。
问题描述
下面我描述下这道题,不过我给的描述是简化版的,实际上再做笔试题的时候,每道题的描述都巨长,一般都会根据实际场景来给出问题的,有些人可能阅读了十几分钟,然后不知道自己要干嘛,我这里给出最简化的版本 。
文章插图
第一题大致是这样,不过不是和原题完全一样哈,在输入和输出有小许区别,因为具体的输入输出我忘了 。我这个描述说简化好像也挺长,不过原题就更加长了 。
解答
文章插图
那么这道题难吗?说实话不难,不过你可以先自己再脑子里想想怎么做比较好,或许在考场上 20 分钟你还真不一定做的出来 。
有些人说,这还不简单,每次询问的时候,我都遍历一下所有人的成绩,这样的花时间复杂度是 O(n * m),显然,如果你这样做,那么是一定通不过的,一定会超时 。一般暴力法能够通过 20% ~ 30% 的测试用力,如果一道题 20 分的话,能拿到 4~6 分 。如果你实在没思路,那么暴力也是个不错的选择 。
1、二分法
这道题我是用二分法做的,就是先对所有人的成绩进行排序,不过排序的时候我们需要开一个新的数组来存储 。然后每次查询的时候可以通过二分查找进行匹配,由于用到了排序,需要花 O(nlogn) 的时间,m 次查询花的时间大致为 O(mlogn) 。所以平均时间复杂度可以算是 O((m+n)logn) 。这个时间复杂度通过所有测试用例,代码如下(没学过java的也能看懂):
文章插图
文章插图
文章插图
这里说明一下,输出的时候我没有输出"%"号哈 。
【2019网易笔试多少分进面试(网易校招笔试竟刷人】前缀和
不过这道题更好的做法是采用前缀和来做 。题设中每个同学的分数不超过 150,不小于 0,那么我们可以用一个数组 arr,然后让 arr[i] 表示分数不超过 i 的人数 。通过这种方式,我们可以把时间复杂度控制在 O(n+m) 。直接看代码吧,会更好理解(这里我就不写输入的代码了,用a[]存放成绩,m[]存放m次询问):
文章插图
这种方法就叫做前缀和,用这种方法简单了很多 。当然前缀和还有其他应用,例如:
如果给你一个数组 arr[],然后进行 m 次询问,每次询问输入两个数 i,j(i
- 2019年4月抖音最热歌曲排名《绿色》上榜,第三歌曲名超长
- 比一般成年女性都高 姚明女儿姚沁蕾2019年多高,九岁身高160cm
- 2019最喜欢的杰尼斯艺人排名山田凉介逆袭夺得榜首
- 2019国漫人气榜单《汉化日记》能让你笑到模糊,不看会可惜
- 三星oe10发布时间
- 网易新闻怎么发布文章具体操作方法介绍
- 再见2018你好2019说说大全告别2018迎接2019句子
- 霸气回应"假的" 网传网易食堂将收费,一张饼就要10元
- 2019成都高中排名,盘点成都最好且升学率最高的五所高中
- 2019抖音十大神曲歌名你会唱哪几首