我最近在一次采访中遇到了这个问题而且我失败了,现在寻找答案.
假设我有一个很大的n个整数数组,所有的不同.
如果这个数组是有序的,我可以将它细分为x个较小的数组,全部大小为y,除了最后一个,可能更少.我可以提取第n个子阵列并将其返回,已经排序.
示例:数组4 2 5 1 6 3.如果y = 2且我想要第二个数组,那么它将是3 4.
现在我所做的只是对数组进行排序并返回第n个子数组,它采用O(n log n).但有人告诉我,有一种方法可以做到这一点O(n + y log y).我在互联网上搜索并没有找到任何东西.想法？