统计米哈游笔试算法题得分

投票
第三题好难,O(nq)的复杂度都超时
全部评论
我们是一张卷子吗 第三题是找子数组个数的那个
点赞 回复 分享
发布于 08-17 22:26 北京
有大佬能指导下第三题吗,我的思路如下: 每个查询可以O(N)得到含有 x的子数组数量。 1. 遍历 数组a 2. 对于两个等于x的位置之间的子数组,长度k,阶乘k!为子数组个数。 3. 总子数组个数减去上述不含x的子数组个数,就得到了含 x 的子数组个数。 阶乘可以预先计算并缓存。
点赞 回复 分享
发布于 08-17 23:27 上海
nq不是铁超时,要qlogn
点赞 回复 分享
发布于 08-18 11:15 上海

相关推荐

点赞 评论 收藏
分享
1 1 评论
分享
牛客网
牛客企业服务