老师这里边界条件是否有误

来源:3-5 快速排序法 - Quick Sort

厥~~~

2019-05-23

老师这里代码是不是有误,l的取值范围应该是sums.length-1才对,而不是nums.length-1。比如nums是0,1,2,3,4一共5个数,sums的长度就是6,但是l的长度最大就是4.显然是不对的。这题是 LeetCode 209题,用二分搜索的算法做的。图片描述

写回答

4回答

厥~~~

提问者

2019-05-23

老师就我刚才说的那个例子。nums长度为5,分别是0,1,2,3,4, sums长度为6,sums[0]=0,sums[1]=0,sums[2]=1,sums[3]=3,sums[4]=6,sums[5]=10, 然后for 语句中l<nums.length-1=5-1=4,所以l最多取3。那sums[l]+s也是最多是sums[3]+s,在下面函数中是在[0,nums.length]也就是[0,6)也就是sums[0,5]范围内找一个解,使得sums[i]>sums[a]+s, a最多取到3, 那万一刚好是{0,1,2,5,7},要找的s是6,长度应该是1,但是这个程序只能跑到2,已经实验过了。leetcode中只是刚好没有这个输入的条件,所以他任务这个代码是正确的,但实际上有BUG。//img.mukewang.com/szimg/5ce614100001d8f611110621.jpg

0
1
liuyubobobo
抱歉,我又看了一下代码,你是对的。我测试的时候好像下意识的把代码修改了。抱歉。正确的应该是 l < nums.length 或者 l < sums.length - 1
2019-05-23
共1条回复

liuyubobobo

2019-05-23

代码没有问题,l是指在nums这个数组中的左边界的位置。在你的例子中,l最多取到4。5已经越过了nums的最右边界。


至于nums和sums之间相差的1个位移,在循环内部被成功处理了。可以尝试制作一个你觉得有问题的测试用例,跟踪一下,看看这个代码是怎样执行的?:)


最后,这个代码取自《玩转算法面试》课程,请下次把问题放到相应课程下。谢谢。


继续加油!:)

0
0

厥~~~

提问者

2019-05-23

0
0

liuyubobobo

2019-05-23

抱歉,这对应的是我哪里的代码,请给我一个链接?

0
0

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程