谷歌 Intern OA

wofaint 发表于 2018-9-29 15:54
第一题比较好的解法应该是用一个 max heap 保留所有字数组的最后一个数字。刚开始 heap 里只有 nums[0]，之 ...

抱歉我刚才想错了，第一次我用的是最小堆所以错了，最大堆应该没问题。你的方法确实应该是时间最好的解法，我那种是时间最坏，如果优化的话可以在arraylist中搜索时用二叉搜索把时间复杂度变成O(nlogn)

wofaint 发表于 2018-9-29 15:54
第一题比较好的解法应该是用一个 max heap 保留所有字数组的最后一个数字。刚开始 heap 里只有 nums[0]，之 ...

这个test case貌似不能过啊：7,8,4,9,1,6,5,7

wofaint 发表于 2018-9-29 15:54
第一题比较好的解法应该是用一个 max heap 保留所有字数组的最后一个数字。刚开始 heap 里只有 nums[0]，之 ...

7,9,6,5,1,8 这个也不行啊。 8进来的时候堆中仅有5和1 这样的话由于8>5需要新开
然而8可以跟在9后边

Wuwei8372 发表于 2018-9-30 00:26
这个test case貌似不能过啊：7,8,4,9,1,6,5,7

大家说的对。我之前给的解法确实是错的。抱歉，没有仔细思考就发了出来。这题不能用 heap。正确的解法应该是这样：开一个 list，这个 list 还是保存每个子数组最后一个元素。然后保持这个 list 是强递增的。刚开始 list 只有 nums[0] 一个元素。然后来新值 nums[i] 时，先看它是不是>= list 中最后一个（即最大值），如果是，说明必须开一个新子数组，这样把它 append 到 list 上边；如果不是，那就二叉搜索 list 中最小的大于 nums[i] 的那个值，然后用 nums[i] 更新该值，也就是更新该子数组的队尾。最后返回值是 list 中元素个数。
这样做法时间复杂度还是 O(n logn)，空间复杂度 O(n)。

Unous 发表于 2018-9-30 00:57
7,9,6,5,1,8 这个也不行啊。 8进来的时候堆中仅有5和1 这样的话由于8>5需要新开
然而8可以跟在9后边

大家说的对。我之前给的解法确实是错的。抱歉，没有仔细思考就发了出来。这题不能用 heap。正确的解法应该是这样：开一个 list，这个 list 还是保存每个子数组最后一个元素。然后保持这个 list 是强递增的。刚开始 list 只有 nums[0] 一个元素。然后来新值 nums[i] 时，先看它是不是>= list 中最后一个（即最大值），如果是，说明必须开一个新子数组，这样把它 append 到 list 上边；如果不是，那就二叉搜索 list 中最小的大于 nums[i] 的那个值，然后用 nums[i] 更新该值，也就是更新该子数组的队尾。最后返回值是 list 中元素个数。
这样做法时间复杂度还是 O(n logn)，空间复杂度 O(n)。

980329498 发表于 2018-9-29 22:54
抱歉我刚才想错了，第一次我用的是最小堆所以错了，最大堆应该没问题。你的方法确实应该是时间最好的解法 ...

大家说的对。我之前给的解法确实是错的。抱歉，没有仔细思考就发了出来。这题不能用 heap。正确的解法应该是这样：开一个 list，这个 list 还是保存每个子数组最后一个元素。然后保持这个 list 是强递增的。刚开始 list 只有 nums[0] 一个元素。然后来新值 nums[i] 时，先看它是不是>= list 中最后一个（即最大值），如果是，说明必须开一个新子数组，这样把它 append 到 list 上边；如果不是，那就二叉搜索 list 中最小的大于 nums[i] 的那个值，然后用 nums[i] 更新该值，也就是更新该子数组的队尾。最后返回值是 list 中元素个数。
这样做法时间复杂度还是 O(n logn)，空间复杂度 O(n)。

楼主能问下是要自己写test case吗还是会像leetcode一样给好test case？

gly612 发表于 2018-10-3 09:04
楼主能问下是要自己写test case吗还是会像leetcode一样给好test case？

点test按钮之后会先跑他给的三个test case，然后跑你自己给的例子，最多可以自己列十个。

题目说的是这个row里面没有比它高的就不需要create一个新的row 所以7,9,6,5,1,8只有两个row吧