苏木三少
错的不是你,而是这个世界。

二分算法-找一对数

题目:

输入n(n<=100,000)个整数,找出其中的两个数,它们之和等于整数m(假定肯定有解)。题中所有整数都能用int表示。

解法1:

用两重循环,枚举所有的取数方法,复杂度是O(n^2)的。

容易超时。

解法2:

1)、将数组排序,复杂度是O(n*log(n))

(2)、对数组中的每个元素a[i],在数组中二分查找m-a[i],看能否找到,复杂度log(n),最坏要查找n-2次,所以查找这部分的复杂度也是O(n*log(n))

这种解法总的复杂度是O(n*log(n))的。

解法3:

(1)、将数组排序,复杂度是O(n*log(n))

(2)、查找的时候,设置两个变量i和j,i的初值是0,j初值是n-1,看a[i]+a[j],如果大于m,将让j减1,直至a[i]+a[j]=m;

这种解法总的复杂度是O(n*log(n))的。

注意:

 

 

赞(2) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » 二分算法-找一对数

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约