请教一个查找算法问题# JobHunting - 待字闺中
b*s
1 楼
电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
，请问是什么算法啊？谢谢
我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
，请问是什么算法啊？谢谢
l*a
2 楼
找最大的 ,考虑一下淘汰赛，n次比较
然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
j*y
3 楼
至少可以优化一下。
假设有 n 个数据, 等分成两部分A, B 每部分有 n / 2个数据
找出 A 中的最大值 A_max 用 (n/2 - 1) 次比较
找出 B中的最大值 B_max 用 (n/2 - 1) 次比较
如果 A_max > B_max 那么， 整个 的最大值是 A_max
下面来找，第二大的值, 这个时候只需 看 (A - {A_max}) Union {B_max}
这 n/2 个数， 找出其中的最大值，就是 整个的第二大的值， 用 (n/2 - 1)次比较。
总共用 3 * (n /2 - 1) 次比较。
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
假设有 n 个数据, 等分成两部分A, B 每部分有 n / 2个数据
找出 A 中的最大值 A_max 用 (n/2 - 1) 次比较
找出 B中的最大值 B_max 用 (n/2 - 1) 次比较
如果 A_max > B_max 那么， 整个 的最大值是 A_max
下面来找，第二大的值, 这个时候只需 看 (A - {A_max}) Union {B_max}
这 n/2 个数， 找出其中的最大值，就是 整个的第二大的值， 用 (n/2 - 1)次比较。
总共用 3 * (n /2 - 1) 次比较。
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
b*s
4 楼
明白了，多谢。
【在 l*****a 的大作中提到】
: 找最大的 ,考虑一下淘汰赛，n次比较
: 然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1
【在 l*****a 的大作中提到】
: 找最大的 ,考虑一下淘汰赛，n次比较
: 然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1
l*b
5 楼
clrs 9.1-1: n + [log n] - 2次比较，不知道是不是要比交次数最少
l*a
6 楼
上面有code吗？
不知道这个思路怎么写code
【在 l*******b 的大作中提到】
: clrs 9.1-1: n + [log n] - 2次比较，不知道是不是要比交次数最少
不知道这个思路怎么写code
【在 l*******b 的大作中提到】
: clrs 9.1-1: n + [log n] - 2次比较，不知道是不是要比交次数最少
l*b
7 楼
没code，大约是这样做：
分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
(3 5) (4 2) (8 7)
---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
回想一下感觉和建堆的复杂度类似
【在 l*****a 的大作中提到】
: 上面有code吗？
: 不知道这个思路怎么写code
分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
(3 5) (4 2) (8 7)
---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
回想一下感觉和建堆的复杂度类似
【在 l*****a 的大作中提到】
: 上面有code吗？
: 不知道这个思路怎么写code
j*y
9 楼
写了一个 code ,不过需要 O((log n)) 的 extra space
first get k = log n;
int * findPath(int A[], int start, int end, int & size)
{
if(start == end)
{
int *result = new int[k];
result[0] = A[start];
size = 1;
return result;
}
int mid = (start + end) / 2;
int size1 = 0, size2 = 0;
int *left = findPath(A, start, mid, size1);
int *right = findPath(A, mid + 1, end, size2);
if(left[0] > right[0])
{
left[size1] = right[0];
size = size1 + 1;
delete right;
return left;
}
else
{
right[size2] = left[0];
size = size2 + 1;
delete left;
return right;
}
}
【在 l*******b 的大作中提到】
: 没code，大约是这样做：
: 分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
: ，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
: (3 5) (4 2) (8 7)
: ---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
first get k = log n;
int * findPath(int A[], int start, int end, int & size)
{
if(start == end)
{
int *result = new int[k];
result[0] = A[start];
size = 1;
return result;
}
int mid = (start + end) / 2;
int size1 = 0, size2 = 0;
int *left = findPath(A, start, mid, size1);
int *right = findPath(A, mid + 1, end, size2);
if(left[0] > right[0])
{
left[size1] = right[0];
size = size1 + 1;
delete right;
return left;
}
else
{
right[size2] = left[0];
size = size2 + 1;
delete left;
return right;
}
}
【在 l*******b 的大作中提到】
: 没code，大约是这样做：
: 分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
: ，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
: (3 5) (4 2) (8 7)
: ---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
b*s
10 楼
没看懂，还是多谢code了。测试了一下，貌似second max不对。。。不管k换成3还是4
，都给第一个72，第二个是69，第三个是70.
int main()
{
int a[10]={39,31,34,53,24,70,42,69,72,44};
int *p;
int size = 0;
p = findPath(a,0,10,size);
cout<cout<cout<cout<getchar();
return 1;
}
【在 j*****y 的大作中提到】
: 写了一个 code ,不过需要 O((log n)) 的 extra space
: first get k = log n;
: int * findPath(int A[], int start, int end, int & size)
: {
: if(start == end)
: {
: int *result = new int[k];
: result[0] = A[start];
: size = 1;
: return result;
，都给第一个72，第二个是69，第三个是70.
int main()
{
int a[10]={39,31,34,53,24,70,42,69,72,44};
int *p;
int size = 0;
p = findPath(a,0,10,size);
cout<cout<cout<cout<getchar();
return 1;
}
【在 j*****y 的大作中提到】
: 写了一个 code ,不过需要 O((log n)) 的 extra space
: first get k = log n;
: int * findPath(int A[], int start, int end, int & size)
: {
: if(start == end)
: {
: int *result = new int[k];
: result[0] = A[start];
: size = 1;
: return result;
c*t
11 楼
弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
★ 发自iPhone App: ChineseWeb 7.7
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
★ 发自iPhone App: ChineseWeb 7.7
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
w*g
12 楼
牛！
【在 l*******b 的大作中提到】
: 没code，大约是这样做：
: 分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
: ，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
: (3 5) (4 2) (8 7)
: ---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
【在 l*******b 的大作中提到】
: 没code，大约是这样做：
: 分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
: ，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
: (3 5) (4 2) (8 7)
: ---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
c*t
13 楼
理论上是，但实际上 最普通的走一遍算法平均也是 n+n/2次比较,因为if a[i] >
current max then it doesn't need to compare with the current second max.
best is n, worst is 2n.
【在 j*****y 的大作中提到】
: 至少可以优化一下。
: 假设有 n 个数据, 等分成两部分A, B 每部分有 n / 2个数据
: 找出 A 中的最大值 A_max 用 (n/2 - 1) 次比较
: 找出 B中的最大值 B_max 用 (n/2 - 1) 次比较
: 如果 A_max > B_max 那么， 整个 的最大值是 A_max
: 下面来找，第二大的值, 这个时候只需 看 (A - {A_max}) Union {B_max}
: 这 n/2 个数， 找出其中的最大值，就是 整个的第二大的值， 用 (n/2 - 1)次比较。
: 总共用 3 * (n /2 - 1) 次比较。
current max then it doesn't need to compare with the current second max.
best is n, worst is 2n.
【在 j*****y 的大作中提到】
: 至少可以优化一下。
: 假设有 n 个数据, 等分成两部分A, B 每部分有 n / 2个数据
: 找出 A 中的最大值 A_max 用 (n/2 - 1) 次比较
: 找出 B中的最大值 B_max 用 (n/2 - 1) 次比较
: 如果 A_max > B_max 那么， 整个 的最大值是 A_max
: 下面来找，第二大的值, 这个时候只需 看 (A - {A_max}) Union {B_max}
: 这 n/2 个数， 找出其中的最大值，就是 整个的第二大的值， 用 (n/2 - 1)次比较。
: 总共用 3 * (n /2 - 1) 次比较。
j*y
14 楼
走一遍好像不行吧？ 比如 10 9 8 7 6 5 4 3
走一遍可以得到 10 和 9 ?
【在 c********t 的大作中提到】
: 理论上是，但实际上 最普通的走一遍算法平均也是 n+n/2次比较,因为if a[i] >
: current max then it doesn't need to compare with the current second max.
: best is n, worst is 2n.
走一遍可以得到 10 和 9 ?
【在 c********t 的大作中提到】
: 理论上是，但实际上 最普通的走一遍算法平均也是 n+n/2次比较,因为if a[i] >
: current max then it doesn't need to compare with the current second max.
: best is n, worst is 2n.
p*2
15 楼
其实这题没那么复杂。就是像你说的就可以了。遍历一遍。
【在 c********t 的大作中提到】
: 弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
:
: ★ 发自iPhone App: ChineseWeb 7.7
p*2
16 楼
为什么不能的到？
【在 j*****y 的大作中提到】
: 走一遍好像不行吧？ 比如 10 9 8 7 6 5 4 3
: 走一遍可以得到 10 和 9 ?
p*2
17 楼
arr=[10,9,8,7,6,5,4,3]
first=arr[0..1].max
second=arr[0..1].min
(2...arr.length).each do |i|
if arr[i]>second
if(arr[i]>first)
second=first
first=arr[i]
else
second=arr[i]
end
end
end
p first
p second
first=arr[0..1].max
second=arr[0..1].min
(2...arr.length).each do |i|
if arr[i]>second
if(arr[i]>first)
second=first
first=arr[i]
else
second=arr[i]
end
end
end
p first
p second
c*t
18 楼
明白了，多谢！
把你说的扩展为n,要开至少n空间，存所有path，（用map好些）divide and conquer,
（如果每次不释放被conquer的数的path的话，还需要更多空间）最后留下最大数，和
它的path，这时候的path应该是lgn的。理论上比较次数为 n+lgn-1，但是存储读写次
数增加很多，时间优化了吗？
【在 l*******b 的大作中提到】
: 没code，大约是这样做：
: 分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
: ，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
: (3 5) (4 2) (8 7)
: ---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
把你说的扩展为n,要开至少n空间，存所有path，（用map好些）divide and conquer,
（如果每次不释放被conquer的数的path的话，还需要更多空间）最后留下最大数，和
它的path，这时候的path应该是lgn的。理论上比较次数为 n+lgn-1，但是存储读写次
数增加很多，时间优化了吗？
【在 l*******b 的大作中提到】
: 没code，大约是这样做：
: 分成n/2对，没一对做比较取较小的一个。这样得到 n/2个数，找到这里面最小的两个
: ，然后用第二小的与最小的那个成对的数比较可以得到n个数里最小的两个
: (3 5) (4 2) (8 7)
: ---> 3 2 7 最小的两个3 2，用3 和 4比较得知2 , 3是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
j*y
19 楼
你这个是找max 和 min 吗？
【在 p*****2 的大作中提到】
: arr=[10,9,8,7,6,5,4,3]
: first=arr[0..1].max
: second=arr[0..1].min
: (2...arr.length).each do |i|
: if arr[i]>second
: if(arr[i]>first)
: second=first
: first=arr[i]
: else
: second=arr[i]
【在 p*****2 的大作中提到】
: arr=[10,9,8,7,6,5,4,3]
: first=arr[0..1].max
: second=arr[0..1].min
: (2...arr.length).each do |i|
: if arr[i]>second
: if(arr[i]>first)
: second=first
: first=arr[i]
: else
: second=arr[i]
l*b
20 楼
嗯，时间不优化吧，比较次数少，但没想出来怎么实现。感觉非常复杂
,
【在 c********t 的大作中提到】
: 明白了，多谢！
: 把你说的扩展为n,要开至少n空间，存所有path，（用map好些）divide and conquer,
: （如果每次不释放被conquer的数的path的话，还需要更多空间）最后留下最大数，和
: 它的path，这时候的path应该是lgn的。理论上比较次数为 n+lgn-1，但是存储读写次
: 数增加很多，时间优化了吗？
,
【在 c********t 的大作中提到】
: 明白了，多谢！
: 把你说的扩展为n,要开至少n空间，存所有path，（用map好些）divide and conquer,
: （如果每次不释放被conquer的数的path的话，还需要更多空间）最后留下最大数，和
: 它的path，这时候的path应该是lgn的。理论上比较次数为 n+lgn-1，但是存储读写次
: 数增加很多，时间优化了吗？
p*2
21 楼
这题不是找max和min
【在 j*****y 的大作中提到】
: 你这个是找max 和 min 吗？
j*y
22 楼
这个比较次数是 2n 吧？
最优的是 n + log n
【在 p*****2 的大作中提到】
: arr=[10,9,8,7,6,5,4,3]
: first=arr[0..1].max
: second=arr[0..1].min
: (2...arr.length).each do |i|
: if arr[i]>second
: if(arr[i]>first)
: second=first
: first=arr[i]
: else
: second=arr[i]
最优的是 n + log n
【在 p*****2 的大作中提到】
: arr=[10,9,8,7,6,5,4,3]
: first=arr[0..1].max
: second=arr[0..1].min
: (2...arr.length).each do |i|
: if arr[i]>second
: if(arr[i]>first)
: second=first
: first=arr[i]
: else
: second=arr[i]
p*2
23 楼
worst case 2n
n+logn需要额外空间吧？
【在 j*****y 的大作中提到】
: 这个比较次数是 2n 吧？
: 最优的是 n + log n
j*y
24 楼
O(log n) 的 extra space
【在 p*****2 的大作中提到】
:
: worst case 2n
: n+logn需要额外空间吧？
【在 p*****2 的大作中提到】
:
: worst case 2n
: n+logn需要额外空间吧？
p*2
25 楼
这个优化真没啥意思。n+log(n)比2n好多少？还需要额外空间。
【在 j*****y 的大作中提到】
: O(log n) 的 extra space
b*s
26 楼
是比较2n次啊。你遍历一遍和遍历两遍不是都要比较2n次吗？如果是worst case的话。
【在 c********t 的大作中提到】
: 弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
:
: ★ 发自iPhone App: ChineseWeb 7.7
【在 c********t 的大作中提到】
: 弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
:
: ★ 发自iPhone App: ChineseWeb 7.7
p*2
27 楼
一般来说常数在时间复杂度的分析中可以忽略
【在 b********s 的大作中提到】
: 是比较2n次啊。你遍历一遍和遍历两遍不是都要比较2n次吗？如果是worst case的话。
b*s
28 楼
我可以确定他不是问时间复杂度，而是问得比较次数，有没有可能小于2n次。我是没想
到，但是他说有的。
【在 p*****2 的大作中提到】
:
: 一般来说常数在时间复杂度的分析中可以忽略
到，但是他说有的。
【在 p*****2 的大作中提到】
:
: 一般来说常数在时间复杂度的分析中可以忽略
相关阅读
读了PHD，最后却得转码工，早知这样，还不如读个masterH1B大潮，问一下加premium加急有没有必要新加坡ncs 招聘 有hadoop 相关经验的朋友[合集] H1B已经拿到收据。还可以同时申请OPT EXTENSION么？H1B transferA家面经 (转载)mobile tester position avaliable in Chicago.H1b premium processing也可以4月1日提交吗？Mathworks Application support engineer 面经 已跪Offer选择求教goldman vs blackrockLCA这玩意儿一定要贴10天吗amazon现在还在发intern的面试吗？网申有很多马甲账号会被拉黑么。。。急问：刚收到offer，但只给了一周的时间考虑，怎么延期offer呢？小本求助方向选择[请教] F1转回H1b的手续和过程 (转载)求助如何追讨被拖欠的2个月工资，之前是OPT正式雇佣关系，人已回国半年Google x lab 是个怎样的地方L是哪个公司？从LCA申请到H1B申请要多久