现在的位置: 首页 > 综合 > 正文

一天一道算法题——数对数目分析

2019年02月16日 ⁄ 综合 ⁄ 共 244字 ⁄ 字号 评论关闭
 题目:
     给定2个数组X和Y,元素都是正数,请找出满足如下条件的数对的个数:
   1.x^y > y^x,即x的y次方大于y的x次方
   2.x来自X数组,y来自Y数组
分析:你真的想要暴力吗,如果两个数组的长度为m和n,那么暴力的复杂度整整有O(m*n)那么高,而且没有用到正数这个条件
我们来变形一下:

x^y>y^x

yx > xy

y/y > x/x


所以,对于数组X,Y计算该值,然后对Y数组排序,对X数组遍历,对于每个x,在Y中进行二分查找


所以现在的时间复杂度为O(nlogn+m*logn)

抱歉!评论已关闭.