找出数对数目

刚看到的一道算法题。

题目

给定两个正数数组X和Y，找出满足下面条件的数对的数目： $x^y>y^x$

分析

设数组长度分别为m,n。暴力解法时间复杂度为$O(m*n)$。但是这样一来正数的条件完全没有用到。尝试变换一下形式，得到$y\log x>x\log y$。更进一步，有$\frac{\log x}{x}>\frac{\log y}{y}$。

所以，对数组X与Y分别计算$\frac{\log x}{x}$,$\frac{\log y}{y}$。然后对Y进行排序，复杂度为$O(n\log n)$。最后遍历X，对每一个X，在Y中进行二分查找。总的时间复杂度为$O(n\log n + m\log n)$。