`
jinghuainfo
  • 浏览: 1515299 次
  • 性别: Icon_minigender_2
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

程序员编程艺术:第五章、寻找满足条件的两个或多个数

 
阅读更多

程序员编程艺术:第五章、寻找满足条件的两个或多个数

作者:July,yansha,zhouzhenren。
致谢:微软100题实现组,编程艺术室。
微博:http://weibo.com/julyweibo
出处:http://blog.csdn.net/v_JULY_v
wiki:http://tctop.wikispaces.com/
------------------------------

前奏

希望此编程艺术系列能给各位带来的是一种方法,一种创造力,一种举一反三的能力。本章依然同第四章一样,选取比较简单的面试题,恭祝各位旅途愉快。同样,有任何问题,欢迎不吝指正。谢谢。


第一节、寻找满足条件的两个数
第14题(数组):
题目:输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

分析

咱们试着一步一步解决这个问题(注意阐述中数列有序无序的区别):

  1. 直接穷举,从数组中任意选取两个数,判定它们的和是否为输入的那个数字。此举复杂度为O(N^2)。很显然,我们要寻找效率更高的解法。
  2. 题目相当于,对每个a[i],然后查找判断sum-a[i]是否也在原始序列中,每一次要查找的时间都要花费为O(N),这样下来,最终找到两个数还是需要O(N^2)的复杂度。那如何提高查找判断的速度列?对了,二分查找,将原来O(N)的查找时间提高到O(logN),这样对于N个a[i],都要花logN的时间去查找相对应的sum-a[i]是否在原始序列中,总的时间复杂度已降为O(N*logN),且空间复杂度为O(1)。(如果有序,直接二分O(N*logN),如果无序,先排序后二分,复杂度同样为O(N*logN+N*logN)=O(N*logN),空间总为O(1))。
  3. 有没有更好的办法列?咱们可以依据上述思路2的思想,a[i]在序列中,如果a[i]+a[k]=sum的话,那么sum-a[i](a[k])也必然在序列中,,举个例子,如下:
    原始序列:1、 2、 4、 7、11、15 用输入数字15减一下各个数,得到对应的序列为:
    对应序列:14、13、11、8、4、 0
    第一个数组以一指针i 从数组最左端开始向右扫描,第二个数组以一指针j 从数组最右端开始向左扫描,如果下面出现了和上面一样的数,即a[*i]=a[*j],就找出这俩个数来了。如上,i,j最终在第一个,和第二个序列中找到了相同的数4和11,,所以符合条件的两个数,即为4+11=15。怎么样,两端同时查找,时间复杂度瞬间缩短到了O(N),但却同时需要O(N)的空间存储第二个数组(@飞羽:要达到O(N)的复杂度,第一个数组以一指针i 从数组最左端开始向右扫描,第二个数组以一指针j 从数组最右端开始向左扫描,首先初始i指向元素1,j指向元素0,谁指的元素小,谁先移动,由于1(i)>0(j),所以i不动,j向左移动。然后j移动到元素4发现大于元素1,故而停止移动j,开始移动i,直到i指向4,这时,i指向的元素与j指向的元素相等,故而判断4是满足条件的第一个数;然后同时移动i,j再进行判断,直到它们到达边界)。
  4. 当然,你还可以构造hash表,正如编程之美上的所述,给定一个数字,根据hash映射查找另一个数字是否也在数组中,只需用O(1)的时间,这样的话,总体的算法通上述思路3 一样,也能降到O(N),但有个缺陷,就是构造hash额外增加了O(N)的空间,此点同上述思路 3。不过,空间换时间,仍不失为在时间要求较严格的情况下的一种好办法。
  5. 如果数组是无序的,先排序(n*logn),然后用两个指针i,j,各自指向数组的首尾两端,令i=0,j=n-1,然后i++,j--,逐次判断a[i]+a[j]?=sum,如果某一刻a[i]+a[j]>sum,则要想办法让sum的值减小,所以此刻i不动,j--,如果某一刻a[i]+a[j]<sum,则要想办法让sum的值增大,所以此刻i++,j不动。所以,数组无序的时候,时间复杂度最终为O(n*logn+n)=O(n*logn),若原数组是有序的,则不需要事先的排序,直接O(n)搞定,且空间复杂度还是O(1),此思路是相对于上述所有思路的一种改进。(如果有序,直接两个指针两端扫描,时间O(N),如果无序,先排序后两端扫描,时间O(N*logN+N)=O(N*logN),空间始终都为O(1))。(与上述思路2相比,排序后的时间开销由之前的二分的n*logn降到了扫描的O(N))。

总结

  • 不论原序列是有序还是无序,解决这类题有以下三种办法:1、二分(若无序,先排序后二分),时间复杂度总为O(n*logn),空间复杂度为O(1);2、扫描一遍X-S[i] 映射到一个数组或构造hash表,时间复杂度为O(n),空间复杂度为O(n);3、两个指针两端扫描(若无序,先排序后扫描),时间复杂度最后为:有序O(n),无序O(n*logn+n)=O(n*logn),空间复杂度都为O(1)。
  • 所以,要想达到时间O(N),空间O(1)的目标,除非原数组是有序的(指针扫描法),不然,当数组无序的话,就只能先排序,后指针扫描法或二分(时间n*logn,空间O(1)),或映射或hash(时间O(n),空间O(n))。时间或空间,必须牺牲一个,自个权衡吧。
  • 综上,若是数组有序的情况下,优先考虑两个指针两端扫描法,以达到最佳的时(O(N)),空(O(1))效应。否则,如果要排序的话,时间复杂度最快当然是只能达到N*logN,空间O(1)则是不在话下。

代码:

ok,在进入第二节之前,咱们先来实现思路5(这里假定数组已经是有序的),代码可以如下编写(两段代码实现):

扩展:
1、如果在返回找到的两个数的同时,还要求你返回这两个数的位置列?
2、如果把题目中的要你寻找的两个数改为“多个数”,或任意个数列?(请看下面第二节)
3、二分查找时: left <= right,right = middle - 1;left < right,right = middle;

//算法所操作的区间,是左闭右开区间,还是左闭右闭区间,这个区间,需要在循环初始化,
//循环体是否终止的判断中,以及每次修改left,right区间值这三个地方保持一致,否则就可能出错.

//二分查找实现一
int search(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n - 1;

while (left <= right)
{
middle = left + (right-left)/2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}

return -1;
}

//二分查找实现二
int search(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n;

while (left < right)
{
middle = left + (right-left)/2;

if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}

return -1;
}


第二节、寻找满足条件的多个数
第21题(数组)
2010年中兴面试题
编程求解:
输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来。

解法一
我想,稍后给出的程序已经足够清楚了,就是要注意到放n,和不放n个区别,即可,代码如下:

解法二
@zhouzhenren:
这个问题属于子集和问题(也是背包问题)。本程序采用 回溯法+剪枝
X数组是解向量,t=∑(1,..,k-1)Wi*Xi, r=∑(k,..,n)Wi
若t+Wk+W(k+1)<=M,则Xk=true,递归左儿子(X1,X2,..,X(k-1),1);否则剪枝;
若t+r-Wk>=M && t+W(k+1)<=M,则置Xk=0,递归右儿子(X1,X2,..,X(k-1),0);否则剪枝;
本题中W数组就是(1,2,..,n),所以直接用k代替WK值。

代码编写如下:

扩展:

1、从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。

2、有两个序列a,b,大小都为n,序列元素的值任意整数,无序;
要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];(微软100题第32题)。

@well:[fairywell]:
给出扩展问题 1 的一个解法:
1、从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
双端 LIS 问题,用 DP 的思想可解,目标规划函数 max{ b[i] + c[i] - 1 }, 其中 b[i] 为从左到右, 0 ~ i 个数之间满足递增的数字个数; c[i] 为从右到左, n-1 ~ i 个数之间满足递增的数字个数。最后结果为 n - max + 1。其中 DP 的时候,可以维护一个 inc[] 数组表示递增数字序列,inc[i] 为从小到大第 i 大的数字,然后在计算 b[i] c[i] 的时候使用二分查找在 inc[] 中找出区间 inc[0] ~ inc[i-1] 中小于 a[i] 的元素个数(low)。
源代码如下:

@yansha:fairywell的程序很赞,时间复杂度O(nlogn),这也是我能想到的时间复杂度最优值了。不知能不能达到O(n)。

扩展题第2题

当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后,a和b的和之差为
A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])

设x = a[i] - b[j],得
|A| - |A'| = |A| - |A-2x|

假设A > 0,

当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,
如果找不到在(0,A)之间的x,则当前的a和b就是答案。

所以算法大概如下:
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。

接上,@yuan:
a[i]-b[j]要接近A/2,则可以这样想,
我们可以对于a数组的任意一个a[k],在数组b中找出与a[k]-C最接近的数(C就是常数,也就是0.5*A)
这个数要么就是a[k]-C,要么就是比他稍大,要么比他稍小,所以可以要二分查找。

查找最后一个小于等于a[k]-C的数和第一个大于等于a[k]-C的数,
然后看哪一个与a[k]-C更加接近,所以T(n) = nlogn。

本章完。


程序员面试题狂想曲-tctop(the crazy thinking of programers)的修订wiki(http://tctop.wikispaces.com/)已建立,我们急切的想得到读者的反馈,意见,建议,以及更好的思路,算法,和代码优化的建议。所以,

•如果你发现了狂想曲系列中的任何一题,任何一章(http://t.cn/hgVPmH)中的错误,问题,与漏洞,欢迎告知给我们,我们将感激不尽,同时,免费赠送本blog内的全部博文集锦的CHM文件1期;
•如果你能对狂想曲系列的创作提供任何建设性意见,或指导,欢迎反馈给我们,并真诚邀请您加入到狂想曲的wiki修订工作中;
•如果你是编程高手,对狂想曲的任何一章有自己更好的思路,或算法,欢迎加入狂想曲的创作组,以为千千万万的读者创造更多的价值,更好的服务。
Ps:狂想曲tctop的wiki修订地址为:http://tctop.wikispaces.com/
。欢迎围观,更欢迎您加入到狂想曲的创作或wiki修订中。

版权所有,本人对本blog内所有任何内容享有版权及著作权。实要转载,请以链接形式注明出处。

分享到:
评论

相关推荐

    程序员编程艺术:面试和算法心得.pdf

    o 2.2 寻找和为定值的两个数 o 2.3 寻找和为定值的多个数 o 2.4 最大连续子数组和 o 2.5 跳台阶 o 2.6 奇偶排序 o 2.7 荷兰国旗 o 2.8 矩阵相乘 o 2.9 完美洗牌 o 2.15 本章习题 第三章 树 o 3.0 本章导读 o 3.1 ...

    Java编程艺术 PDF

    Herbert Schildt 和James Holmes两位编程大师通过将Java应用于某些有趣、实用的计算机问题和编程任务中,全面展示了Java语言的强大功能、敏捷性、多样性和艺术性。本书各章内容分别涉及到Java精髓、递归下降的表达式...

    《C++编程艺术》教程+代码

    第5章 Internet文件下载工具 131 5.1 WinINet库 131 5.2 文件下载工具子系统 132 5.2.1 操作的一般理论 137 5.2.2 download()函数 137 5.2.3 ishttp()函数 142 5.2.4 httpverOK()函数 142 5.2.5 getfname()函数 143 ...

    java 编程艺术

    Herbert Schildt 和James Holmes两位编程大师通过将Java应用于某些有趣、实用的计算机问题和编程任务中,全面展示了Java语言的强大功能、敏捷性、多样性和艺术性。本书各章内容分别涉及到Java精髓、递归下降的表达式...

    代码之美(中文完整版).pdf

    第5章 正确、优美、迅速(按重要性排序):从设计XML验证器中学到的经验 5.1 XML验证器的作用 5.2 问题所在 5.3 版本1:简单的实现 5.4 版本2:模拟BNF语法——复杂度O(N) 5.5 版本3:第一个复杂度O(log N)的优化 5.6 ...

    C#编程经验技巧宝典

    98 &lt;br&gt;0153 如何自定义数字小数点左边分组位数 98 &lt;br&gt;0154 格式化输入数据为货币格式 99 &lt;br&gt;0155 如何计算两个整数的乘积 99 &lt;br&gt;0156 如何将二进制数转换为十进制数 100 &lt;br&gt;0157 如何...

    十五个经典算法研究与总结、目录+索引(定稿版)

    可以这么说,开博头俩个月一直在整理微软等公司的面试题,而后的四个月至今,则断断续续,除了继续微软面试100题系列,和程序员编程艺术系列之外,便在写这经典算法研究系列和相关算法文章。 本经典算法研究系列...

    二十三种设计模式【PDF版】

    会 Java 的人越来越多,但是一直徘徊在语言层次的程序员不在少数,真正掌握 Java 中接口或抽象类的应用不是很多,大家 经常以那些技术只适合大型项目为由,避开或忽略它们,实际中,Java 的接口或抽象类是真正体现 ...

    openGL 参考手册

    第5章 OpenGL参考说明 本书的主体部分,它包括各组相关的OpenGL命令的描述。带参数的命令和与之一起描述的其他命令仅在数据类型方面有所不同。每个函数的参考说明介绍了参数、命令的作用和使用这些命令时可能发生...

    opengl Manual

    第5章 OpenGL参考说明 本书的主体部分,它包括各组相关的OpenGL命令的描述。带参数的命令和与之一起描述的其他命令仅在数据类型方面有所不同。每个函数的参考说明介绍了参数、命令的作用和使用这些命令时可能发生...

    PHP开发实战1200例(第1卷).(清华出版.潘凯华.刘中华).part1

    第5章 会话应用 333 5.1 COOKIE 334 实例255 控制登录用户的过期时间 334 实例256 自动登录 335 实例257 单击登录 336 实例258 统计用户在线时间 339 实例259 限制用户访问网站的时间 340 实例260 用户来访时客户端...

    PHP开发实战1200例(第1卷).(清华出版.潘凯华.刘中华).part2

    第5章 会话应用 333 5.1 COOKIE 334 实例255 控制登录用户的过期时间 334 实例256 自动登录 335 实例257 单击登录 336 实例258 统计用户在线时间 339 实例259 限制用户访问网站的时间 340 实例260 用户来访时客户端...

Global site tag (gtag.js) - Google Analytics