世界最大搜索引擎OA

匿名用户-6M4OX *2018-10-1 22:55:58* · 2018-10-1 22:55:58

fluu 发表于 2018-10-1 22:54
讨论一下第二题就是把两个数组排序，然后用两个指针从头到尾扫一遍？

第二个数组排序的话，你的输出会很难对应。

匿名用户-6M4OX *2018-10-1 22:57:56* · 2018-10-1 22:57:56

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

aquazi

我对问题一感到困惑。你能给我解决方案吗？

匿名用户-6M4OX *2018-10-2 03:06:27* · 2018-10-2 03:06:27

aquazi 发表于 2018-10-2 01:46
我对问题一感到困惑。你能给我解决方案吗？

维护一个vector储存每一个分组当前最小值。每一次插入新值时用二分查找找最合适的位置添加元素，没有的话就添加一个新的。

aquazi

你只对每组的最后一个元素使用二进制搜索？

匿名用户-6M4OX *2018-10-2 08:09:21* · 2018-10-2 08:09:21

aquazi 发表于 2018-10-2 04:55
你只对每组的最后一个元素使用二进制搜索？

对，因为题目要求只能站在每组的最后面，组内不能插队。所以如果要达到严格递减，你插入的新元素只要比当前本组最后一个元素小就够了。前面的没有必要管，也没有空间管。

baz

感谢分享～ Good Luck ～

Malcol

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Malcol

论坛匿名用户发表于 2018-10-1 22:55
第二个数组排序的话，你的输出会很难对应。

这题如果用python写的话其实两个都排序更好一些时间复杂度是O(m+n) 但用java的话还要自己实现个类。。

匿名用户-6M4OX *2018-10-9 02:11:51* · 2018-10-9 02:11:51

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式