请问我自己写了个二分法但超时是哪里的问题
来源:3-6 对撞指针 Two Sum II - Input Array is Sorted
夜的钢琴曲5
2019-10-19
public class TwoSum2 {
public int[] twoSum(int[] numbers, int target) {
return binarySearch(numbers,target);
}
private int[] binarySearch(int[] arr,int target) {
int l = 0;
int r = arr.length;
int mid = (l + r) / 2;
int[] index = new int[2];
for (int i = 0; i < arr.length; i++) {
while (l < r) {
if (arr[i] + arr[mid] == target) {
index[0] = i;
index[1] = mid;
break;
}
if (arr[i] + arr[mid] < target)
l = mid + 1;
if (arr[i] + arr[mid] > target)
r = mid - 1;
}
}
return index;
}
public static void main(String[] args) {
int[] num = {2,7,11,5};
int t = 9;
TwoSum2 twoSum2 = new TwoSum2();
String s = twoSum2.twoSum(num,t).toString();
System.out.println(s);
}
}
波波老师,对于leetcode167题的二分法,我自己写了个办法,但不知道为什么上传的话是超时,然后我写了个测试,但是没返回。而且我debug时只有在打印的那一行标记断点才有意义,但那一行debug也没返回,我反复检查了几次,都没发现逻辑问题,请问代码时哪里有问题呢?
写回答
1回答
-
首先,你的测试用例有问题。
167 问题保证传入的数组是有序的,二分搜索法也必须在有序数组上运行。你的测试数组不是有序的。
其次,r 的初值应该为 arr.length - 1,请再回顾一下课程的 3-1;3-2 两个小节,理解清楚为什么。
然后,l,r,mid 的定义,应该 for 循环内。每一轮 for 循环,重新运行一遍二分搜索。你将这些二分搜索使用的变量定义在循环外面,上一轮循环改变的 l,r,mid 值会影响下一次二分搜索。
这些问题都修改完以后,对于这个题目,还包含搜索到的索引是相同的问题(如果你将代码修改正确了,提交给 Leetcode,就会明白了),可以思考一下怎么解决?然后,再回顾一下课程给出的参考代码?
==========
P.S. debug 的意义是要一步一步跟程序。一步一步看,程序走在每一行,数据是如何变化的,和你想要的逻辑是否一致。如果不一致,自己到底哪里想错了。或者为什么无法执行到某个点,为什么执行不下去了。只是打一个断点,是没有意义的。
继续加油!:)
012019-10-20
相似问题
关于leetcode88题的一个小问题
回答 1
两个面经问题
回答 1