citadel店面

哦懂了有更快的办法……对不起是我太弱了，同学说这只是easy难度……

yz9 发表于 2020-5-12 16:01
哦懂了有更快的办法……对不起是我太弱了，同学说这只是easy难度……

方便说一下解法吗？实在想不出有什么能比nlogn更快的

lk2 发表于 2020-5-22 09:32
方便说一下解法吗？实在想不出有什么能比nlogn更快的

一般思路是：你想一下现有的解法哪些步骤是多余的，如何去掉

hmm 感觉把input array按照given的order 放进bst（假设他是ordered）
然后直接recursive over the tree, maintain lower和upperbound （这个过程和实际binary search就一样）
然后每个node如果他符合当前的interval就是可以了