老师这里边界条件是否有误
来源: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。
012019-05-23 -
liuyubobobo
2019-05-23
代码没有问题,l是指在nums这个数组中的左边界的位置。在你的例子中,l最多取到4。5已经越过了nums的最右边界。
至于nums和sums之间相差的1个位移,在循环内部被成功处理了。可以尝试制作一个你觉得有问题的测试用例,跟踪一下,看看这个代码是怎样执行的?:)
最后,这个代码取自《玩转算法面试》课程,请下次把问题放到相应课程下。谢谢。
继续加油!:)
00 -
厥~~~
提问者
2019-05-23
00 -
liuyubobobo
2019-05-23
抱歉,这对应的是我哪里的代码,请给我一个链接?
00
相似问题