网易 4.21算法笔试 蹲个第三四题的题解或思路

网易算法笔试 蹲个第三四题的题解或思路#网易笔试#
全部评论
素筛法得到数据范围所有素数,数组排序,然后将数组中所有数换成小于等于自身的第一个素数。找到中位数,对数组中每个元素,统计中位数到自身相差几个素数。(素筛法的时候可以存下是第几个素数)。 然后对于前半段元素,如果是非1且非素数且小于中位数的话,多统计了一次(因为可以将它变为比自己大的素数),需要减掉。 这种思路过了90😂,感觉太麻烦,且没法证明。
1 回复 分享
发布于 2022-04-21 21:32
第三题,先质数筛找到所有的质数,然后对整个数组排序,可以证明对于两个数a,b,以及a,b之间的质数集合c,a,b到c中任何质数的操作和是一样的,双指针从两边一对对的删除pair,然后最中间情况分奇数偶数考虑一下(剩一个奇质数不操作,否则加1),a,b之间没有质数的情况也要考虑一下 (一起加一or减一就是2次操作?) (事后诸葛亮昨晚没做出来也不知道能过多少
1 回复 分享
发布于 2022-04-22 09:49

相关推荐

10-28 14:42
门头沟学院 Java
watermelon1124:因为嵌入式炸了
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务