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 广东

相关推荐

勇敢大角牛2:项目太基础了。小demo就不要往简历中写了,得分是什么鬼,大作业?。并且项目经历和你的求职意向岗位不匹配,没有体现硬件的亮点。话有点糙,还请谅解
点赞 评论 收藏
分享
评论
2
3
分享
牛客网
牛客企业服务