|   登录   |   注册   |   设为首页   |   加入收藏   

用户登录

close

用户名:

密码:

新用户注册

close

用户名:

密码:

密码确认:

电子邮箱:

关注内容:

个人主页:

帮助

close

龙宇网成立于2008年3月,网站进入整体运作于2010年10月1日。

在这里,我们把它做成了一个真正意义上的网站,完全以个人的信息为内容,以网友的需要为主导,全力搜罗各种信息,建立完善的网站功能,使网友在这里可以第一时间找到所需要的信息。

现在,经过三年的努力,网站的资料已经相当丰富,而网站得到了大家的喜爱和认可。

但,我们还是会继续努力下去,让网间的这份快乐继续持续下去,让这份闲暇时的日子,与快乐一并同行。

寻觅快乐,网住快乐,关注网络,是龙宇网的宣言与承诺。

问题: Google 面试题1 数组补丁

发布时间:2016-06-23 16:15:06 浏览次数:653


给出一个从小到大排好序的整数数组nums和一个整数n,在数组中添加若干个补丁(元素)使得[1,n]的区间内的所有数都可以表示成nums中若干个数的和。返回最少需要添加的补丁个数。
Example 1:
nums = [1, 3], n = 6
返回1,表示至少需要添加1个数{2},才可以表示1到6之间所有数。
Example 2:
nums = [1, 5, 10], n = 20
返回2,表示至少需要添加两个数{2,4},才可以表示1到20之间所有数。





回答

读者不难想到暴力搜索的做法:先穷举每一个不在数组里的数p,再穷举判断p是否可以表示为数组中若干个数的和;如果不能,则把p加入数组中,把答案加一。

然而,这种做法时间复杂度高且实际操作难度大(需要考虑穷举的顺序)。我们不妨先思考一个简单的问题,如果nums数组为空,那么最少需要多少个数字才能表示1到n之间所有数?相信大家都可以想到一个贪心算法,即按照1、2、4、8...都顺序添加,每次加入都数都比之前所有数的总和大1,直到总和大于n。本题的难点是预先给出了一些数,但这不影响我们的贪心策略:假设nums当前至多可以表示1到m之间的所有数,加入m+1;直到m大于等于n。

标签: google面试
19
17