h***n
发帖数: 276 | 1 很常见的一道题，
N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
大的数为第二大的数。我的问题是怎么写代码？谢谢！ |
n*s
发帖数: 752 | 2 类似于quick sort?
间。
【在 h***n 的大作中提到】
: 很常见的一道题，
: N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
: 算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
: 大的数为第二大的数。我的问题是怎么写代码？谢谢！
|
h***n
发帖数: 276 | 3 算法是先要找最大数，然后利用其中的信息找到第二大数，quicksort中的partition没
有这层含义把
我只是想知道怎么用O(1)的空间实现n+log(n)-2的复杂度，因为好像没有人讨论
【在 n*s 的大作中提到】
: 类似于quick sort?
:
: 间。
|
i**********e
发帖数: 1145 | 4 类似二分.
Hint: tournament match.
Below has a great description of this method.
Maybe the code can be simplified more using recursion.
http://www.seeingwithc.org/topic3html.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
h**********d
发帖数: 4313 | 5 用两个variable分别存最大数和第二大数
你说两两比较找最大数的同时，顺便用第二个variable update第二大数
是这样吗？
间。
【在 h***n 的大作中提到】
: 很常见的一道题，
: N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
: 算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
: 大的数为第二大的数。我的问题是怎么写代码？谢谢！
|
S**I
发帖数: 15689 | 6 就是用quick sort里的partition来实现；C++ STL algorithm里的nth_element和
partial_sort就是干这个的，具体实现见：
http://blogs.msdn.com/b/devdev/archive/2006/01/18/514482.aspx
【在 h***n 的大作中提到】
: 算法是先要找最大数，然后利用其中的信息找到第二大数，quicksort中的partition没
: 有这层含义把
: 我只是想知道怎么用O(1)的空间实现n+log(n)-2的复杂度，因为好像没有人讨论
|
l********f
发帖数: 149 | 7 Heap sort N-1, 然后 reheap一下搞定 |
i**9
发帖数: 351 | 8 i don't think this can be done without using extra memory.
间。
【在 h***n 的大作中提到】
: 很常见的一道题，
: N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
: 算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
: 大的数为第二大的数。我的问题是怎么写代码？谢谢！
|
c********t
发帖数: 5706 | 9 这个好。实现了n+lg(n)-2的time. 可是lz说不需要额外空间啊？
不管是你的方法还是quick sort，都必须要额外的空间吧？
【在 i**********e 的大作中提到】
: 类似二分.
: Hint: tournament match.
: Below has a great description of this method.
: Maybe the code can be simplified more using recursion.
: http://www.seeingwithc.org/topic3html.html
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
c********t
发帖数: 5706 | 10 不行，你这样复杂度是 2n-3
【在 h**********d 的大作中提到】
: 用两个variable分别存最大数和第二大数
: 你说两两比较找最大数的同时，顺便用第二个variable update第二大数
: 是这样吗？
:
: 间。
|
c********t
发帖数: 5706 | 11 好像是不可能。要么要存比较过哪些数，要么要存原始的index位置(swap)。我想了想
，没想通，抛砖引玉,说说我的想法吧。
O(1) space. 就是可以有variable. 如果只用swap，就可以做到要求。
比如ihasleetcode的方法，如果能不用空间保存和最大数比较过的数就可以实现。我延
伸一下，两两比较如果swap大的数到前面。那么得出最大数(第一个数）的同时，如果
知道了它原始的index。从这个index应该有方法知道，都比较过哪些数，比如 第2个数
最大，那么最后就应该和 2，3，5，9，17... 2^i+1... 比较过。第11个数最大，最后
就应该和9，11，12，17，...2^i+1比较过。这些比较过数里的最大的就是second max.
所以是lg(n)-1
可是我的难题是第一，没有储存原始index。第二，虽然有规律，但还不知道如何算哪
些index比较过。
用quick sort + swap 也类似，好像知道最大数比较过的patition最左边数再比较就可
以知道second。
【在 i**9 的大作中提到】
: i don't think this can be done without using extra memory.
:
: 间。
|
