o********n
发帖数: 193 | 1 本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
iterative binary search，好像写起来更简单点，起码不会出大bug。
各位大牛觉得是不是这么回事？ | B*******1
发帖数: 2454 | 2 什么题？ 贴来具体看看。
【在 o********n 的大作中提到】
: 本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
: 不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
: 下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
: iterative binary search，好像写起来更简单点，起码不会出大bug。
: 各位大牛觉得是不是这么回事？
| o********n
发帖数: 193 | 3 Given a huge sorted integer array A, and there are huge duplicates in the
array. Given an integer T, inert T to the array, if T already exisit, insert
it at the end of duplicates.
Find the insert point. The signature:
int FindInsertionPosition(int A[], int size, int T);
For example:
A[15] = {2,5,7,8,8,8,8,8,8,8,8,8,8,8,9}
If T == 6, return 2;
If T == 8' return 14 | j*****y
发帖数: 1071 | 4 int FindInsertionPosition(int A[], int size, int T)
{
int left = 0, right = size - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(T < A[mid])
{
right = mid;
}
else
{
left = mid + 1;
}
}
if(A[left] > T)
{
return left;
}
else
{
return left + 1;
}
}
insert
【在 o********n 的大作中提到】
: Given a huge sorted integer array A, and there are huge duplicates in the
: array. Given an integer T, inert T to the array, if T already exisit, insert
: it at the end of duplicates.
: Find the insert point. The signature:
: int FindInsertionPosition(int A[], int size, int T);
: For example:
: A[15] = {2,5,7,8,8,8,8,8,8,8,8,8,8,8,9}
: If T == 6, return 2;
: If T == 8' return 14
| p*****2
发帖数: 21240 | | o********n
发帖数: 193 | 6 二爷，这题难度你看是几？
你要面这题，考点是不是 bug free?
【在 p*****2 的大作中提到】
: 我有总结
: http://blog.sina.com.cn/s/blog_b9285de20101h88j.html
| B********t
发帖数: 147 | 7 我记得有重复元素的不能这么弄吧。。。150上的原题啊。
【在 j*****y 的大作中提到】
: int FindInsertionPosition(int A[], int size, int T)
: {
: int left = 0, right = size - 1;
: while(left < right)
: {
: int mid = (left + right) / 2;
: if(T < A[mid])
: {
: right = mid;
: }
| p*****2
发帖数: 21240 | 8
http://leetcode.cloudfoundry.com/
这上边有难度
【在 o********n 的大作中提到】
: 二爷，这题难度你看是几？
: 你要面这题，考点是不是 bug free?
| l*****a
发帖数: 14598 | 9 总结太泛泛
列出了几种区别，但是根本没提什么情况下该用哪种，以及为什么用那种
觉得没有帮助。
其实这种题最好的办法就是用while(lo
然后直接用lo=mid or hi=mid
最后判断a[hi]a[lo]即可
yishan大虾上次用了while(lo
【在 p*****2 的大作中提到】
: 我有总结
: http://blog.sina.com.cn/s/blog_b9285de20101h88j.html
| o********n
发帖数: 193 | 10 二爷，我这题不再你的列表里啊，那是不是难度为0？
【在 p*****2 的大作中提到】
:
: http://leetcode.cloudfoundry.com/
: 这上边有难度
| | | o********n
发帖数: 193 | 11 我也糊弄了一个iterative的：
int FindInsertionPoint(int A[], int size, int T)
{
int left = 0;
int right = size - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (T < A[mid])
right = mid - 1;
else if (T == A[mid] && ((mid == size - 1) || A[mid + 1] != T))
return mid + 1;
else
left = mid + 1;
}
if (T < A[left])
return left;
else
return left + 1;
} | o********n
发帖数: 193 | 12 楼上大牛们，我跑了下justtry的code，都对。我的那个明显拙劣，也对。
下面该整个recrusive版本的了。 | p*****2
发帖数: 21240 | 13 我写了一个练练
def findPosition(arr:Array[Int], target:Int):Int={
def bsearch(start:Int, end:Int):Int={
if(start==end) return end
val mid=start+(end-start)/2
arr(mid)-target match{
case x if x<=0 =>bsearch(mid+1,end)
case _ => bsearch(start,mid)
}
}
bsearch(0,arr.size)
} | p*****2
发帖数: 21240 | 14
做了一下，三分题吧。或者2.5
你第二个答案是不是错的？
【在 o********n 的大作中提到】
: 二爷，我这题不再你的列表里啊，那是不是难度为0？
| o********n
发帖数: 193 | 15 我刚才各种case都测了, 两个方案都没错。我的思路比较愚直，还没跳出找数子的套路
，而楼上大虾比较潇洒。性能上，对A4找6,我的一下子命中直接返回，而楼上大侠的还
得往后半区继续找下去。
void Test()
{
int A1[1] = {4};
int A2[2] = {4, 5};
int A3[8] = {2,4,6,6,6,6,6,9};
int A4[8] = {2,4,6,6,8,8,8,9};
int point = FindInsertionPoint(A1, 1, 1);
point = FindInsertionPoint(A1, 1, 10);
point = FindInsertionPoint(A2, 2, 1);
point = FindInsertionPoint(A2, 2, 10);
for (int i = 0; i <= 10; i++)
{
point = FindInsertionPoint(A3, 8, i);
point = FindInsertionPoint(A4, 8, i);
}
}
【在 p*****2 的大作中提到】
:
: 做了一下，三分题吧。或者2.5
: 你第二个答案是不是错的？
| l*******b
发帖数: 2586 | 16 square root那个binary search太难了... | o********n
发帖数: 193 | 17 是，一直在找没有什么简单明了表述方法，能把recursion的前面几步和最后几步的
state一步一步写在纸上，保证思路清晰不会出死循环。
【在 l*******b 的大作中提到】
: square root那个binary search太难了...
| c********t
发帖数: 5706 | 18 f(A,8)应该返回14吧。
int findInsertionPosition(int A[], int T) {
int left = 0, right = A.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] <= T)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
【在 o********n 的大作中提到】
: 本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
: 不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
: 下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
: iterative binary search，好像写起来更简单点，起码不会出大bug。
: 各位大牛觉得是不是这么回事？
| p*****2
发帖数: 21240 | 19
A[15] = {2,5,7,8,8,8,8,8,8,8,8,8,8,8,9}
If T == 6, return 2;
If T == 8' return 15
第二个不应该是14吗？
【在 o********n 的大作中提到】
: 我刚才各种case都测了, 两个方案都没错。我的思路比较愚直，还没跳出找数子的套路
: ，而楼上大虾比较潇洒。性能上，对A4找6,我的一下子命中直接返回，而楼上大侠的还
: 得往后半区继续找下去。
: void Test()
: {
: int A1[1] = {4};
: int A2[2] = {4, 5};
: int A3[8] = {2,4,6,6,6,6,6,9};
: int A4[8] = {2,4,6,6,8,8,8,9};
: int point = FindInsertionPoint(A1, 1, 1);
| o********n
发帖数: 193 | 20 你对，我改过来了。
【在 c********t 的大作中提到】
: f(A,8)应该返回14吧。
:
: int findInsertionPosition(int A[], int T) {
: int left = 0, right = A.length - 1;
: while (left <= right) {
: int mid = left + (right - left) / 2;
: if (A[mid] <= T)
: left = mid + 1;
: else
: right = mid - 1;
| | | c********t
发帖数: 5706 | 21 A4里面又没有7，为啥你能一下子命中返回？
【在 o********n 的大作中提到】
: 我刚才各种case都测了, 两个方案都没错。我的思路比较愚直，还没跳出找数子的套路
: ，而楼上大虾比较潇洒。性能上，对A4找6,我的一下子命中直接返回，而楼上大侠的还
: 得往后半区继续找下去。
: void Test()
: {
: int A1[1] = {4};
: int A2[2] = {4, 5};
: int A3[8] = {2,4,6,6,6,6,6,9};
: int A4[8] = {2,4,6,6,8,8,8,9};
: int point = FindInsertionPoint(A1, 1, 1);
| o********n
发帖数: 193 | 22 你看我这笨的，找6,我改了。
【在 c********t 的大作中提到】
: A4里面又没有7，为啥你能一下子命中返回？
| o********n
发帖数: 193 | 23 coldknight大牛的答案也对，好像是最简洁明快的版本，应该没有更好的了。 | c********t
发帖数: 5706 | 24 我是青蛙一只，你如果想提前返回，还可以在最前加上
if (T < A[mid] && ((mid == 0) || A[mid - 1] <= T)) return mid;
不过真心不建议你写提前返回，不光是这道题，大部分题都是，这样会自己增加你面试
难度。
【在 o********n 的大作中提到】
: coldknight大牛的答案也对，好像是最简洁明快的版本，应该没有更好的了。
| p*****2
发帖数: 21240 | 25
能不能测测是我程序？
【在 o********n 的大作中提到】
: coldknight大牛的答案也对，好像是最简洁明快的版本，应该没有更好的了。
| o********n
发帖数: 193 | 26 二爷，抱歉，没运行环境，暂时没法测。
【在 p*****2 的大作中提到】
:
: 能不能测测是我程序？
| o********n
发帖数: 193 | 27 帮你改成c code了，不知道是不是改错了，跑起来stack overflow。
int FindInsertionPointBS(int A[], int start, int end, int T)
{
if(start==end)
return start;
int mid=end-(end-start)/2;
if (A[mid] <= T)
return FindInsertionPointBS(A, mid+1,end, T);
else
return FindInsertionPointBS(A, start,end, T);
}
int FindInsertionPoint(int A[], int size, int T)
{
return FindInsertionPointBS(A, 0, size - 1, T);
} | o********n
发帖数: 193 | 28 谢大侠
【在 c********t 的大作中提到】
: 我是青蛙一只，你如果想提前返回，还可以在最前加上
: if (T < A[mid] && ((mid == 0) || A[mid - 1] <= T)) return mid;
: 不过真心不建议你写提前返回，不光是这道题，大部分题都是，这样会自己增加你面试
: 难度。
| p*****2
发帖数: 21240 | 29
这一行有问题吧？
return FindInsertionPointBS(A, start,end, T);
【在 o********n 的大作中提到】
: 帮你改成c code了，不知道是不是改错了，跑起来stack overflow。
: int FindInsertionPointBS(int A[], int start, int end, int T)
: {
: if(start==end)
: return start;
: int mid=end-(end-start)/2;
: if (A[mid] <= T)
: return FindInsertionPointBS(A, mid+1,end, T);
: else
: return FindInsertionPointBS(A, start,end, T);
| o********n
发帖数: 193 | 30 改成这样了，测了下，也爆栈啊。
int FindInsertionPointBS(int A[], int start, int end, int T)
{
if(start==end)
return start;
int mid=end-(end-start)/2;
if (A[mid] <= T)
return FindInsertionPointBS(A, mid+1,end, T);
else
return FindInsertionPointBS(A, start,mid, T);
}
int FindInsertionPoint(int A[], int size, int T)
{
return FindInsertionPointBS(A, 0, size - 1, T);
} | | | p*****2
发帖数: 21240 | 31
你用的什么数据呀？
【在 o********n 的大作中提到】
: 改成这样了，测了下，也爆栈啊。
: int FindInsertionPointBS(int A[], int start, int end, int T)
: {
: if(start==end)
: return start;
: int mid=end-(end-start)/2;
: if (A[mid] <= T)
: return FindInsertionPointBS(A, mid+1,end, T);
: else
: return FindInsertionPointBS(A, start,mid, T);
| o********n
发帖数: 193 | 32 问题出在这行，粗心了，改成mid = start+(end-start)/2, 就通过。
int mid=end-(end-start)/2; | p*****2
发帖数: 21240 | 33
这个应该改成
if(start>=end) return end吧。刚才好像是有点问题。
你有test case share吗？我想自己测测。
【在 o********n 的大作中提到】
: 改成这样了，测了下，也爆栈啊。
: int FindInsertionPointBS(int A[], int start, int end, int T)
: {
: if(start==end)
: return start;
: int mid=end-(end-start)/2;
: if (A[mid] <= T)
: return FindInsertionPointBS(A, mid+1,end, T);
: else
: return FindInsertionPointBS(A, start,mid, T);
| p*****2
发帖数: 21240 | 34
我这次是想往上取的。因此应该最后的结果是end才多。
你改一下if(start>=end) return end帮我试试好吗？
【在 o********n 的大作中提到】
: 问题出在这行，粗心了，改成mid = start+(end-start)/2, 就通过。
: int mid=end-(end-start)/2;
| o********n
发帖数: 193 | 35 test case：
#include
void BinarySearch_Test()
{
int A1[1] = {4};
int A2[2] = {4, 5};
int A3[8] = {2,4,6,6,6,6,6,9};
int A4[8] = {2,4,6,6,8,8,8,9};
cout << FindInsertionPoint(A1, 1, 1) << endl;
cout << FindInsertionPoint(A1, 1, 10) << endl;
cout << FindInsertionPoint(A2, 2, 1) << endl;
cout << FindInsertionPoint(A2, 2, 10) << endl;
for (int i = 0; i <= 10; i++)
cout << i << "=" << FindInsertionPoint(A3, 8, i) << " ";
cout << endl;
for (int i = 0; i <= 10; i++)
cout << i << "=" << FindInsertionPoint(A4, 8, i) << " ";
cout << endl;
} | o********n
发帖数: 193 | 36 改成if(start>=end) return end，然后用int mid=end-(end-start)/2；还是爆栈。 | o********n
发帖数: 193 | | o********n
发帖数: 193 | 38 #include
void BinarySearch_Test()
{
int A1[1] = {4};
int A2[2] = {4, 5};
int A3[8] = {2,4,6,6,6,6,6,9};
int A4[8] = {2,2,6,6,8,8,9,9};
bool success = true;
success &= FindInsertionPoint(A1, 1, 1) == 0;
success &= FindInsertionPoint(A1, 1, 10) == 1;
success &= FindInsertionPoint(A2, 2, 1) == 0;
success &= FindInsertionPoint(A2, 2, 10) == 2;
success &= FindInsertionPoint(A3, 8, 0) == 0;
success &= FindInsertionPoint(A3, 8, 1) == 0;
success &= FindInsertionPoint(A3, 8, 2) == 1;
success &= FindInsertionPoint(A3, 8, 3) == 1;
success &= FindInsertionPoint(A3, 8, 4) == 2;
success &= FindInsertionPoint(A3, 8, 5) == 2;
success &= FindInsertionPoint(A3, 8, 6) == 7;
success &= FindInsertionPoint(A3, 8, 7) == 7;
success &= FindInsertionPoint(A3, 8, 8) == 7;
success &= FindInsertionPoint(A3, 8, 9) == 8;
success &= FindInsertionPoint(A3, 8, 10) == 8;
success &= FindInsertionPoint(A4, 8, 0) == 0;
success &= FindInsertionPoint(A4, 8, 1) == 0;
success &= FindInsertionPoint(A4, 8, 2) == 2;
success &= FindInsertionPoint(A4, 8, 3) == 2;
success &= FindInsertionPoint(A4, 8, 4) == 2;
success &= FindInsertionPoint(A4, 8, 5) == 2;
success &= FindInsertionPoint(A4, 8, 6) == 4;
success &= FindInsertionPoint(A4, 8, 7) == 4;
success &= FindInsertionPoint(A4, 8, 8) == 6;
success &= FindInsertionPoint(A4, 8, 9) == 8;
success &= FindInsertionPoint(A4, 8, 10) == 8;
cout << (success ? "passed" : "failed") << endl;
} | p*****2
发帖数: 21240 | 39
多谢。代码更新了。
0
1
0
2
0
0
1
1
2
2
7
7
7
8
8
0
0
2
2
2
2
4
4
6
8
8
【在 o********n 的大作中提到】
: #include
: void BinarySearch_Test()
: {
: int A1[1] = {4};
: int A2[2] = {4, 5};
: int A3[8] = {2,4,6,6,6,6,6,9};
: int A4[8] = {2,2,6,6,8,8,9,9};
: bool success = true;
: success &= FindInsertionPoint(A1, 1, 1) == 0;
: success &= FindInsertionPoint(A1, 1, 10) == 1;
| c********t
发帖数: 5706 | 40 试试把return FindInsertionPointBS(A, start,mid, T);
改成 return FindInsertionPointBS(A, start,mid-1, T);
【在 o********n 的大作中提到】
: 改成这样了，测了下，也爆栈啊。
: int FindInsertionPointBS(int A[], int start, int end, int T)
: {
: if(start==end)
: return start;
: int mid=end-(end-start)/2;
: if (A[mid] <= T)
: return FindInsertionPointBS(A, mid+1,end, T);
: else
: return FindInsertionPointBS(A, start,mid, T);
| | | o********n
发帖数: 193 | 41 糊弄了个recursive版本，test passed.
之前一直爆栈，不断debug才走到这步的，要是在白板上写，被官看出爆栈，肯定就挂
了。
int FindInsertionPointBS(int A[], int left, int right, int T)
{
if (left >= right)
{
if (A[left] <= T)
return left + 1;
else
return left;
}
int mid = left + (right - left) / 2;
if (T < A[mid])
return FindInsertionPointBS(A, left, mid - 1, T);
else
return FindInsertionPointBS(A, mid + 1, right, T);
}
int FindInsertionPoint(int A[], int size, int T)
{
return FindInsertionPointBS(A, 0, size - 1, T);
} | o********n
发帖数: 193 | 42 tricky的地方一个是 if (left >= right)而不是left == right
另一个是二分的时候，中点已不是sub problem，抛弃不考虑。
想法比较愚笨。 | p*****2
发帖数: 21240 | 43
你看看我调整了之后的程序？
【在 o********n 的大作中提到】
: 糊弄了个recursive版本，test passed.
: 之前一直爆栈，不断debug才走到这步的，要是在白板上写，被官看出爆栈，肯定就挂
: 了。
: int FindInsertionPointBS(int A[], int left, int right, int T)
: {
: if (left >= right)
: {
: if (A[left] <= T)
: return left + 1;
: else
| o********n
发帖数: 193 | | p*****2
发帖数: 21240 | 45
13
【在 o********n 的大作中提到】
: 更新在几楼？
| o********n
发帖数: 193 | 46 不爆栈，但test failed, 错在
A = {4}， T = 10; (left == end) so it returns end (0). answer is 1;
Converted C code:
int FindInsertionPointBS(int A[], int start, int end, int T)
{
if (start == end)
return end;
int mid = start + (end - start) / 2;
if (A[mid] <= T)
return FindInsertionPointBS(A, mid + 1, end, T);
else
return FindInsertionPointBS(A, start, mid, T);
}
int FindInsertionPoint(int A[], int size, int T)
{
return FindInsertionPointBS(A, 0, size - 1, T);
} | p*****2
发帖数: 21240 | 47
return FindInsertionPointBS(A, 0, size - 1, T);
}
把size-1 改称 size
【在 o********n 的大作中提到】
: 不爆栈，但test failed, 错在
: A = {4}， T = 10; (left == end) so it returns end (0). answer is 1;
: Converted C code:
: int FindInsertionPointBS(int A[], int start, int end, int T)
: {
: if (start == end)
: return end;
: int mid = start + (end - start) / 2;
: if (A[mid] <= T)
: return FindInsertionPointBS(A, mid + 1, end, T);
| o********n
发帖数: 193 | 48 Passed!
二爷版recursive实现，简单明了：
int FindInsertionPointBS(int A[], int start, int end, int T)
{
if (start == end)
return end;
int mid = start + (end - start) / 2;
if (A[mid] <= T)
return FindInsertionPointBS(A, mid + 1, end, T);
else
return FindInsertionPointBS(A, start, mid, T);
}
int FindInsertionPoint(int A[], int size, int T)
{
return FindInsertionPointBS(A, 0, size, T);
} | p*****2
发帖数: 21240 | 49
多谢你。binary search确实比较tricky，不能太着急写，得小心。
【在 o********n 的大作中提到】
: Passed!
: 二爷版recursive实现，简单明了：
: int FindInsertionPointBS(int A[], int start, int end, int T)
: {
: if (start == end)
: return end;
: int mid = start + (end - start) / 2;
: if (A[mid] <= T)
: return FindInsertionPointBS(A, mid + 1, end, T);
: else
| p*g
发帖数: 141 | 50
/// 有意思的是, 这里用 right = mid-1; 也对
呵呵
【在 j*****y 的大作中提到】
: int FindInsertionPosition(int A[], int size, int T)
: {
: int left = 0, right = size - 1;
: while(left < right)
: {
: int mid = (left + right) / 2;
: if(T < A[mid])
: {
: right = mid;
: }
| | | p*g
发帖数: 141 | | p*****2
发帖数: 21240 | 52
我可以访问呀。
【在 p*g 的大作中提到】
: this link is broken
| o********n
发帖数: 193 | 53 继续学习二爷难度列表里所有的binary search问题，发现难度很大，search 2D
matrix发现比powerx,y难，但二叶给的难度只有3，压力很大啊。 | o********n
发帖数: 193 | 54 Search 2D matrix 我把题目看歪了！我以为The first integer of each row is
greater than the first integer of the previous row,所以有这种组合：
1 4 9
2 3 6
3 4 5
这种组合，明显也能优化，不用一行行搞，哪位大牛实现一个^_^ | o********n
发帖数: 193 | 55 题目如下
Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the FIRST integer of the
previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[2, 3, 4, 5],
[3, 30, 34, 50]
]
4 return true | o***d
发帖数: 313 | 56 it looks like mine works, too. do you have more test cases?
p.s. why can't I use cterm to copy a formated segment of code...
int FindInsertionPosition(int A[], int size, int T)
{
int l=0;
int h=size-1;
int m=0;
while(l<=h)
{
m=(h+l)/2;
if (T
h=m-1;
else
l=m+1;
}
return l;
}
【在 o********n 的大作中提到】
: 本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
: 不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
: 下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
: iterative binary search，好像写起来更简单点，起码不会出大bug。
: 各位大牛觉得是不是这么回事？
|
|
