【待字闺中】数对数目

题目:

给定两个数组X和Y,元素都是正数。请找出满足一下条件的数对的数目:

1.x^y>y^x,即x的y次方>y的x次方

2.x来自X数组,y来自Y数组

分析,

一。暴力搜索。

X数组长度m,Y数组长度n, 复杂度o(m*n)

二。数学变换。

log(x)/x>log(y)/y

1.数组X,Y分别代入f(a)=log(a)/a

2.对Y进行排序O(nlogn)

3.遍历X数组,对于每一个x,在Y中,进行二分查找,即可。

所以,总的复杂度为 O(nlogn+mlogn)

//注意:排序和二分,复杂度不清楚。

原文地址:https://www.cnblogs.com/karcylee/p/3952530.html