Chinaunix首页 | 论坛 | 博客
  • 博客访问: 17353
  • 博文数量: 12
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 115
  • 用 户 组: 普通用户
  • 注册时间: 2014-04-29 08:49
文章分类

全部博文(12)

文章存档

2014年(12)

分类: IT职场

2014-07-18 15:41:30

输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

因为是递增数组,所以第一次求出a[low]+a[high]==k,则是乘积最小的那个。
当两个数x+y=k,当x和y越接近乘机越大。证明如下:

x+y=k

两边平方:

(x+y)^2=k^2

然后继续变:

(x-y)^2+4xy=k^2

很显然x和y越接近,xy就越大。故让x和y尽量相差很大。

从两边往中间扫描即可,O(N)时间

阅读(310) | 评论(0) | 转发(0) |
0

上一篇:移位运算注意

下一篇:没有了

给主人留下些什么吧!~~