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. : : 间。
|