求教一道老题 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 求教一道老题

相关主题
● 一道老题但是以前的解好象都不对
● 二叉树如何判断一个节点是不是在另外两个节点的path上。。。。好像是个老题了。。求解？
● 问个老题，find the next larger in BST
● 有谁知道geniusxsy整理的CLRS章节的帖子在哪不？
● 问10个老题
● G一道题
● leetcode insert interval 为什么没人用binary search?
● LinkedIn面试题请教
● 翻出一道老题来
● 问一道题(2)

相关话题的讨论汇总
话题: logn话题: 第二名话题: 冠军话题: 问题话题: 二分法

进入JobHunting版参与讨论

(共1页)

c****s
发帖数: 241

这个是geniusxsy总结的题，但是没有看懂。不知哪位能指点一下？
题目4. 很简单的，N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数
，不需要额外空间。这个是典型的问题本身就是答案提示的题目--基于比较又有LogN，
很显然思路涉及二分法，继续下去，剩下的问题就仅仅是找一个符合要求的Implementa
tion了。

m*****k
发帖数: 731

you sure it is logN? not ceil(3N/2)-2 ?

h*****a
发帖数: 1992

这个就像打网球比赛，无种子的淘汰赛，要把第一名和第二名找出来。
第一名当然是全胜的那个。第二名呢，不一定是在决赛输的那个。也许真正的第二名运
气不好，第一轮就碰了最后的冠
军，结果输掉了。那么谁有可能是第二名呢? 只有被冠军打败过的人才有可能是第二名
。所以要安排所有被冠军打败过的人
再搞一次淘汰塞。这个淘汰塞里的冠军就是真正的第二名。
关键是要多少场赛事才能确定这个冠军和第二名。如果有n个选手，那两两淘汰，决出
冠军要n-1场比赛。在这过程中，冠
军总共打了logN场比赛，所以第二名就从这logN个失败的选手中再两两淘汰。所以要决
出第二名还要logN-1场。
所以总共就是(n-1)+(logn-1)=n+logn-2场比赛

Implementa

【在 c****s 的大作中提到】

: 这个是geniusxsy总结的题，但是没有看懂。不知哪位能指点一下？
: 题目4. 很简单的，N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数
: ，不需要额外空间。这个是典型的问题本身就是答案提示的题目--基于比较又有LogN，
: 很显然思路涉及二分法，继续下去，剩下的问题就仅仅是找一个符合要求的Implementa
: tion了。

d********2
发帖数: 135

正解～～～

【在 h*****a 的大作中提到】

: 这个就像打网球比赛，无种子的淘汰赛，要把第一名和第二名找出来。
: 第一名当然是全胜的那个。第二名呢，不一定是在决赛输的那个。也许真正的第二名运
: 气不好，第一轮就碰了最后的冠
: 军，结果输掉了。那么谁有可能是第二名呢? 只有被冠军打败过的人才有可能是第二名
: 。所以要安排所有被冠军打败过的人
: 再搞一次淘汰塞。这个淘汰塞里的冠军就是真正的第二名。
: 关键是要多少场赛事才能确定这个冠军和第二名。如果有n个选手，那两两淘汰，决出
: 冠军要n-1场比赛。在这过程中，冠
: 军总共打了logN场比赛，所以第二名就从这logN个失败的选手中再两两淘汰。所以要决
: 出第二名还要logN-1场。

S**Y
发帖数: 136

need o(n) space

【在 d********2 的大作中提到】

: 正解～～～

c****s
发帖数: 241

明白了，多谢多谢。另外再送一个包子。:)

【在 h*****a 的大作中提到】

g******i
发帖数: 354

解释得简洁明了，太牛了。
很多的算法，看上去很难，但要是都能像heyihua的解释，清晰明了，就会好学多
了。

【在 h*****a 的大作中提到】

w****z
发帖数: 288

good solution! niu!!

【在 h*****a 的大作中提到】

P****i
发帖数: 1362

how? I thought it is O(n^2) for quick index

【在 S**Y 的大作中提到】

: need o(n) space

c*****y
发帖数: 90

谢谢。我有个疑问：题目中说了不需要额外空间，可是保留所有与最后冠军比赛过的选
手是需要额外空间的。是我理解有什么错误吗？

【在 h*****a 的大作中提到】

相关主题
● 有谁知道geniusxsy整理的CLRS章节的帖子在哪不？
● 问10个老题
● G一道题
● leetcode insert interval 为什么没人用binary search?
进入JobHunting版参与讨论

c*******d
发帖数: 255

re

【在 c*****y 的大作中提到】

: 谢谢。我有个疑问：题目中说了不需要额外空间，可是保留所有与最后冠军比赛过的选
: 手是需要额外空间的。是我理解有什么错误吗？

b*******K
发帖数: 62

请教一个问题，一个是跟冠军比赛的选手如何保存，这是不是需要额外的空间。
另外一个就是用二分法是不是比这种解决方法更优化。
比如分成两部分，每个部分都求出最大的和第二大的。然后递归求解，直到每组只剩2
个选手。这个复杂度是O(4logn)吧？感觉应该能解决这个问题。不知道是不是有没有想
到的问题，请指教。

【在 h*****a 的大作中提到】

c****s
发帖数: 241

关于space，我的理解是直接在数组做，程序run完了之后，第一个和第二个就是最大和
第二大。
第二个分析有问题。heyihua的文章里面已经用了二分法了。

2

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

: 请教一个问题，一个是跟冠军比赛的选手如何保存，这是不是需要额外的空间。
: 另外一个就是用二分法是不是比这种解决方法更优化。
: 比如分成两部分，每个部分都求出最大的和第二大的。然后递归求解，直到每组只剩2
: 个选手。这个复杂度是O(4logn)吧？感觉应该能解决这个问题。不知道是不是有没有想
: 到的问题，请指教。

B*****t
发帖数: 335

you are right! without extra space, you cannot make it.
actually this is a problem in CLRS(2dn edition)，Exercise 9.1-1

【在 c*****y 的大作中提到】

: 谢谢。我有个疑问：题目中说了不需要额外空间，可是保留所有与最后冠军比赛过的选
: 手是需要额外空间的。是我理解有什么错误吗？

b*******K
发帖数: 62

请问一下分析有什么问题？能否具体解释一下？谢谢

【在 c****s 的大作中提到】

: 关于space，我的理解是直接在数组做，程序run完了之后，第一个和第二个就是最大和
: 第二大。
: 第二个分析有问题。heyihua的文章里面已经用了二分法了。
:
: 2

B*****t
发帖数: 335

这个题不是问题复杂度是多少，是问最少需要多少比较次数。
就算是求复杂度，也不是O(4logn)

2

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

(共1页)

进入JobHunting版参与讨论

相关主题
● 问一道题(2)
● 二维排序数组的查找正解是O(M+N)的复杂度吗
● 问一道题
● 真慫阿, Facebook 1st phone interview,
● google phone interview
● 上楼梯问题的时间复杂度是o(n)还是 nlogn?
● 备考google onsite, 讨论堆排序的时间复杂度
● 周末出道题
● 数组里找第二大的数
● 这么多G的面经，我也想想～～

相关话题的讨论汇总
话题: logn话题: 第二名话题: 冠军话题: 问题话题: 二分法

boards