Robinhood 面经

teletype 发表于 2020-8-24 05:10
第四题可以用greedy + binary search解，O(nlogn)

我觉得找出diff里面最大的一项|ai - bi|中的ai, 然后在a中找到和bi最接近的一个值替换应该就行了吧，o(n), 还是说我理解错了?

HR.W 发表于 2020-9-11 04:10
我觉得找出diff里面最大的一项|ai - bi|中的ai, 然后在a中找到和bi最接近的一个值替换应该就行了吧，o(n) ...

这个应该有反例的。greedy的条件是对b中每一个数用binary search找a中和它最接近的数。我当时过了全部case

teletype 发表于 2020-9-11 05:47
这个应该有反例的。greedy的条件是对b中每一个数用binary search找a中和它最接近的数。我当时过了全部cas ...

en,  你的是对的, 你对每一个b中的元素用类似于quick sort的binary select方法，然后看哪一个组合的diff和之前比最小, 是nlogn。

第二题除了暴力还有其他办法吗