logo
Redian新闻
>未名空间
>PhotoGear - 摄影器材
>
又想买新的 kindle 了
avatar
又想买新的 kindle 了# PhotoGear - 摄影器材
o*n
1 楼
本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
iterative binary search，好像写起来更简单点，起码不会出大bug。
各位大牛觉得是不是这么回事？
avatar
n*r
2 楼
这个照片是不是就是最后绿卡上的照片？
avatar
b*n
3 楼
avatar
B*1
4 楼
什么题？ 贴来具体看看。

【在 o********n 的大作中提到】
: 本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
: 不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
: 下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
: iterative binary search，好像写起来更简单点，起码不会出大bug。
: 各位大牛觉得是不是这么回事？
avatar
y*0
5 楼
不是。
fingerprint的时候的照片是绿卡照片。
avatar
c*y
6 楼
什么时候贝神买东西开始这么犹豫了？
avatar
o*n
7 楼
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
avatar
i*9
8 楼
照片要求不能带眼镜，不能带帽子，不能包头巾（穆斯林可以），不能化浓妆。男人可
以留长发，留大胡子，女人可以剃光头，剃眉毛。
avatar
b*n
9 楼
因为手里已经有一个 kindle 2 了，要是没有我就买了

【在 c********y 的大作中提到】
: 什么时候贝神买东西开始这么犹豫了？
avatar
j*y
10 楼
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
avatar
n*r
11 楼
眼镜呢？不带眼镜照照片，应该没有什么问题吧？看老印的论坛说有人因为眼镜被RFE

【在 y******0 的大作中提到】
: 不是。
: fingerprint的时候的照片是绿卡照片。
avatar
x*c
12 楼
just buy it, holy docs don't have any trouble with reselling or 100 dollar
cash.
avatar
y*0
14 楼
自娱自乐的照片除外，什么证件照让带过眼镜？

RFE

【在 n********r 的大作中提到】
: 眼镜呢？不带眼镜照照片，应该没有什么问题吧？看老印的论坛说有人因为眼镜被RFE
avatar
w*i
15 楼
just sell one of your gears and use the profit to buy it...

【在 b******n 的大作中提到】

avatar
l*g
17 楼
Why don't you guys read the official instruction?
This is from the official I485 instruction form:
http://www.uscis.gov/sites/default/files/files/form/i-485instr.
4. Photos
You must submit two identical color photographs of
yourself taken within 30 days of the filing of this
application. The photos must have a white to off-white
background, be printed on thin paper with a glossy finish,
and be unmounted and unretouched.
Passport-style photos must be 2" x 2." The photos must
be in color with full face, frontal view on a white to off-
white background. Head height should measure 1" to 1
3/8" from top of hair to bottom of chin, and eye height is
between 1 1/8" to 1 3/8" from bottom of photo. Your
head must be bare unless you are wearing a headwear as
required by a religious order of which you are a member.
Using pencil or felt pen, lightly print your name and Alien
Registration Number (A-Number) on the back of the
photo.
avatar
A*1
18 楼
那就买
avatar
B*t
19 楼
我记得有重复元素的不能这么弄吧。。。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;
: }
avatar
n*e
21 楼
感觉还是DX好，就是太贵了
avatar
p*2
22 楼

http://leetcode.cloudfoundry.com/
这上边有难度

【在 o********n 的大作中提到】
: 二爷，这题难度你看是几？
: 你要面这题，考点是不是 bug free?
avatar
F*n
23 楼
哈哈，版主有所不知了
485证件照可以戴眼镜，不过不能有反光，要能清楚的看到瞳孔。

【在 y******0 的大作中提到】
: 自娱自乐的照片除外，什么证件照让带过眼镜？
:
: RFE
avatar
b*n
24 楼
手持DXG淡定的飘过。。。
avatar
l*a
25 楼
总结太泛泛
列出了几种区别，但是根本没提什么情况下该用哪种，以及为什么用那种
觉得没有帮助。
其实这种题最好的办法就是用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
avatar
y*0
26 楼
好吧，凡是照证件照，我主动摘眼镜....

【在 F*********n 的大作中提到】
: 哈哈，版主有所不知了
: 485证件照可以戴眼镜，不过不能有反光，要能清楚的看到瞳孔。
avatar
o*n
27 楼
二爷，我这题不再你的列表里啊，那是不是难度为0？

【在 p*****2 的大作中提到】
:
: http://leetcode.cloudfoundry.com/
: 这上边有难度
avatar
t*n
28 楼
我也是，我觉得不带眼镜更帅

【在 y******0 的大作中提到】
: 好吧，凡是照证件照，我主动摘眼镜....
avatar
o*n
29 楼
我也糊弄了一个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;
}
avatar
a*m
30 楼
不戴眼镜俺不知道相机在哪里肿么办?

【在 t********n 的大作中提到】
: 我也是，我觉得不带眼镜更帅
avatar
o*n
31 楼
楼上大牛们，我跑了下justtry的code，都对。我的那个明显拙劣，也对。
下面该整个recrusive版本的了。
avatar
m*r
32 楼
戴眼镜不反光
官方文件上写的。
avatar
p*2
33 楼
我写了一个练练
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)
}
avatar
p*e
34 楼
自拍时不要闪光，就不会有什么眼镜反光的问题。
avatar
p*2
35 楼

做了一下，三分题吧。或者2.5
你第二个答案是不是错的？

【在 o********n 的大作中提到】
: 二爷，我这题不再你的列表里啊，那是不是难度为0？
avatar
k*g
36 楼
镜片一反光，就完
avatar
o*n
37 楼
我刚才各种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
: 你第二个答案是不是错的？
avatar
l*b
38 楼
square root那个binary search太难了...
avatar
o*n
39 楼
是，一直在找没有什么简单明了表述方法，能把recursion的前面几步和最后几步的
state一步一步写在纸上，保证思路清晰不会出死循环。

【在 l*******b 的大作中提到】
: square root那个binary search太难了...
avatar
c*t
40 楼
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。
: 各位大牛觉得是不是这么回事？
avatar
p*2
41 楼

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);
avatar
o*n
42 楼
你对，我改过来了。

【在 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;
avatar
c*t
43 楼
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);
avatar
o*n
44 楼
你看我这笨的，找6,我改了。

【在 c********t 的大作中提到】
: A4里面又没有7，为啥你能一下子命中返回？
avatar
o*n
45 楼
coldknight大牛的答案也对，好像是最简洁明快的版本，应该没有更好的了。
avatar
c*t
46 楼
我是青蛙一只，你如果想提前返回，还可以在最前加上
if (T < A[mid] && ((mid == 0) || A[mid - 1] <= T)) return mid;
不过真心不建议你写提前返回，不光是这道题，大部分题都是，这样会自己增加你面试
难度。

【在 o********n 的大作中提到】
: coldknight大牛的答案也对，好像是最简洁明快的版本，应该没有更好的了。
avatar
p*2
47 楼

能不能测测是我程序？

【在 o********n 的大作中提到】
: coldknight大牛的答案也对，好像是最简洁明快的版本，应该没有更好的了。
avatar
o*n
48 楼
二爷，抱歉，没运行环境，暂时没法测。

【在 p*****2 的大作中提到】
:
: 能不能测测是我程序？
avatar
o*n
49 楼
帮你改成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);
}
avatar
o*n
50 楼
谢大侠

【在 c********t 的大作中提到】
: 我是青蛙一只，你如果想提前返回，还可以在最前加上
: if (T < A[mid] && ((mid == 0) || A[mid - 1] <= T)) return mid;
: 不过真心不建议你写提前返回，不光是这道题，大部分题都是，这样会自己增加你面试
: 难度。
avatar
p*2
51 楼

这一行有问题吧？
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);
avatar
o*n
52 楼
改成这样了，测了下，也爆栈啊。
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);
}
avatar
p*2
53 楼

你用的什么数据呀？

【在 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);
avatar
o*n
54 楼
问题出在这行，粗心了，改成mid = start+(end-start)/2, 就通过。
int mid=end-(end-start)/2;
avatar
p*2
55 楼

这个应该改成
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);
avatar
p*2
56 楼

我这次是想往上取的。因此应该最后的结果是end才多。
你改一下if(start>=end) return end帮我试试好吗？

【在 o********n 的大作中提到】
: 问题出在这行，粗心了，改成mid = start+(end-start)/2, 就通过。
: int mid=end-(end-start)/2;
avatar
o*n
57 楼
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;
}
avatar
o*n
58 楼
改成if(start>=end) return end，然后用int mid=end-(end-start)/2；还是爆栈。
avatar
o*n
59 楼
你等下，我把test case改成自动的。
avatar
o*n
60 楼
#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;
}
avatar
p*2
61 楼

多谢。代码更新了。
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;
avatar
c*t
62 楼
试试把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);
avatar
o*n
63 楼
糊弄了个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);
}
avatar
o*n
64 楼
tricky的地方一个是 if (left >= right)而不是left == right
另一个是二分的时候，中点已不是sub problem，抛弃不考虑。
想法比较愚笨。
avatar
p*2
65 楼

你看看我调整了之后的程序？

【在 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
avatar
o*n
66 楼
更新在几楼？
avatar
p*2
67 楼

13

【在 o********n 的大作中提到】
: 更新在几楼？
avatar
o*n
68 楼
不爆栈，但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);
}
avatar
p*2
69 楼

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);
avatar
o*n
70 楼
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);
}
avatar
p*2
71 楼

多谢你。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
avatar
p*g
72 楼

/// 有意思的是, 这里用 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;
: }
avatar
p*2
74 楼

我可以访问呀。

【在 p*g 的大作中提到】
: this link is broken
avatar
o*n
75 楼
继续学习二爷难度列表里所有的binary search问题，发现难度很大，search 2D
matrix发现比powerx,y难，但二叶给的难度只有3，压力很大啊。
avatar
o*n
76 楼
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
这种组合，明显也能优化，不用一行行搞，哪位大牛实现一个^_^
avatar
o*n
77 楼
题目如下
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
avatar
o*d
78 楼
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。
: 各位大牛觉得是不是这么回事？
相关阅读
核灾难已不可避免：日本放弃抢救核电站已全面撤退 (转载)佳能股价几天还涨了时隔7年，那恐怖的一幕又出现了 (转载)KEH的老相机"UG"可以买吗上几张xpan[FS] Panasonic GF1rw T1i 换镜头最被畸形爆炒的相机——排行表（投票）干燥箱？Pentax终于汇报灾情了麻烦大家评论一下用过NEX真是没法用别的了请教新加坡什么地方有卖Pentax器材的？500cm白色的GF2要不要取消？现在看来，最关键的是神医们，赶紧屯红圈啊，佳能厂房塌了贪师你的粮食今天亏大了【长期求购】Epson R1900 @$320+ML严重庆祝加班即将结束 心情好 奔！！ (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。