b********s
发帖数: 1676 | 1 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
，请问是什么算法啊？谢谢 |
l*****a
发帖数: 14598 | 2 找最大的 ,考虑一下淘汰赛，n次比较
然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
|
j*****y
发帖数: 1071 | 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次
: ，请问是什么算法啊？谢谢
|
b********s
发帖数: 1676 | 4 明白了，多谢。
【在 l*****a 的大作中提到】
: 找最大的 ,考虑一下淘汰赛，n次比较
: 然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1
|
l*******b
发帖数: 2586 | 5 clrs 9.1-1: n + [log n] - 2次比较，不知道是不是要比交次数最少 |
l*****a
发帖数: 14598 | 6 上面有code吗？
不知道这个思路怎么写code
【在 l*******b 的大作中提到】
: clrs 9.1-1: n + [log n] - 2次比较，不知道是不是要比交次数最少
|
l*******b
发帖数: 2586 | 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
|
M**A
发帖数: 78 | 8 int find_max_sec(int *a, int n) {
if(n<2) return 0;
int max, sec_max;
if(a[1]
max=a[0];
sec_max=a[1];
}
else {
max=a[1];
sec_max=a[0];
}
for(int i=2;i
if(a[i]>max) {
sec_max=max;
max=a[i];
}
if(a[i]sec_max){
sec_max=a[i];
}
}
cout<<"Largest element is "<
cout<<"Second largest element is"<
return 1;
} |
j*****y
发帖数: 1071 | 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是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
|
b********s
发帖数: 1676 | 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<<"max="<
cout<<"second max="<
cout<<"p[3]="<
cout<<"p[4]="<
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
发帖数: 5706 | 11 弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
★ 发自iPhone App: ChineseWeb 7.7
【在 b********s 的大作中提到】
: 电面问道，给一个数组n个数字，找出最大的数。然后找出第二大的数。
: 我当时用了最简单的方式比较2n次。找出2个数。但是面试的说有更好的算法小于2n次
: ，请问是什么算法啊？谢谢
|
w***g
发帖数: 5958 | 12 牛！
【在 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
发帖数: 5706 | 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) 次比较。
|
j*****y
发帖数: 1071 | 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.
|
p*****2
发帖数: 21240 | 15
其实这题没那么复杂。就是像你说的就可以了。遍历一遍。
【在 c********t 的大作中提到】
: 弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
:
: ★ 发自iPhone App: ChineseWeb 7.7
|
p*****2
发帖数: 21240 | 16
为什么不能的到？
【在 j*****y 的大作中提到】
: 走一遍好像不行吧？ 比如 10 9 8 7 6 5 4 3
: 走一遍可以得到 10 和 9 ?
|
p*****2
发帖数: 21240 | 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 |
c********t
发帖数: 5706 | 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是所有里面最小的两个
: 回想一下感觉和建堆的复杂度类似
|
j*****y
发帖数: 1071 | 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]
|
l*******b
发帖数: 2586 | 20 嗯，时间不优化吧，比较次数少，但没想出来怎么实现。感觉非常复杂
,
【在 c********t 的大作中提到】
: 明白了，多谢！
: 把你说的扩展为n,要开至少n空间，存所有path，（用map好些）divide and conquer,
: （如果每次不释放被conquer的数的path的话，还需要更多空间）最后留下最大数，和
: 它的path，这时候的path应该是lgn的。理论上比较次数为 n+lgn-1，但是存储读写次
: 数增加很多，时间优化了吗？
|
|
|
p*****2
发帖数: 21240 | 21
这题不是找max和min
【在 j*****y 的大作中提到】
: 你这个是找max 和 min 吗？
|
j*****y
发帖数: 1071 | 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]
|
p*****2
发帖数: 21240 | 23
worst case 2n
n+logn需要额外空间吧？
【在 j*****y 的大作中提到】
: 这个比较次数是 2n 吧？
: 最优的是 n + log n
|
j*****y
发帖数: 1071 | 24 O(log n) 的 extra space
【在 p*****2 的大作中提到】
:
: worst case 2n
: n+logn需要额外空间吧？
|
p*****2
发帖数: 21240 | 25
这个优化真没啥意思。n+log(n)比2n好多少？还需要额外空间。
【在 j*****y 的大作中提到】
: O(log n) 的 extra space
|
b********s
发帖数: 1676 | 26 是比较2n次啊。你遍历一遍和遍历两遍不是都要比较2n次吗？如果是worst case的话。
【在 c********t 的大作中提到】
: 弱问一句，难道不是遍历一遍就可以找出来两个最大的数吗？
:
: ★ 发自iPhone App: ChineseWeb 7.7
|
p*****2
发帖数: 21240 | 27
一般来说常数在时间复杂度的分析中可以忽略
【在 b********s 的大作中提到】
: 是比较2n次啊。你遍历一遍和遍历两遍不是都要比较2n次吗？如果是worst case的话。
|
b********s
发帖数: 1676 | 28 我可以确定他不是问时间复杂度，而是问得比较次数，有没有可能小于2n次。我是没想
到，但是他说有的。
【在 p*****2 的大作中提到】
:
: 一般来说常数在时间复杂度的分析中可以忽略
|
