首页 > 代码库 > 【待字闺中】数对数目
【待字闺中】数对数目
题目:
给定两个数组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)
//注意:排序和二分,复杂度不清楚。
【待字闺中】数对数目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。