pdd Java后端笔试第四题求解

根据输入n个长度的数组,根据hash函数 f(x) = x/n,求原序列,如果有多种情况,输出最小字典序

测试用例1

输入:

5 (数组长度5)

-1 1 -1 3 4 (根据hash计算后的序列, -1 表示这个位置没有元素放入)

输出

1 3 4(原序列)

测试用例2

输入

5

9 1 8 3 4

输出

1 3 4 9 8

解释:

-1 -1 -1 -1 -1 --> -1 1 -1 -1 -1 --> -1 1 -1 3 -1 --> -1 1 -1 3 4 --> 9 1 -1 3 4 --> 9 1 8 3 4

全部评论
判断一个位置 i 的值 a[i] ,放在这里的条件是必须 a[i]%n 到 i 位置的数都要比 a[i] 先填进数组里面。 可以得到一个拓扑排序,之后就好求解了。 但如果单纯是拓扑排序,只能得80%,会出现n^2的边爆空间。 之后,我估计要建虚点优化,但我没时间写了。 第三题卡了1h的分类讨论,只剩20m写了。
点赞 回复 分享
发布于 2024-08-12 11:47 广东

相关推荐

06-26 18:30
门头沟学院 Java
据说名字越长别人越关...:你问问这里面有多少是正经候选人,而不是乱打招呼的
点赞 评论 收藏
分享
05-09 14:45
门头沟学院 Java
点赞 评论 收藏
分享
白火同学:大二有这水平很牛了,可以适当对关键信息加粗一点,比如关键技术、性能指标之类的。
点赞 评论 收藏
分享
评论
2
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务