从一个未排序的列表,找第 k 个

lzcgsong
lzcgsong 2010-11-25 字数 59

线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

谢谢

Algorithm 算法
41 个回复
Leimiaos
3WATER 2010-11-25

快速排序

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

Nein
Ja 2010-11-25

人家要求线性时间呢

【 在 Leimiaos (3WATER) 的大作中提到: 】

: 标  题: Re: 从一个未排序的列表,找第 k 个

: 发信站: 水木社区 (Thu Nov 25 00:10:17 2010), 站内

: 快速排序

: 【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: : 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: : 谢谢

: --

:     ▏                                                                      

    ▏             ●                  ●                       ╭---╮     

    ▏    ╭---╮       ╭---┳---╮        ╭---╮    ╭---╮  │          

    ▏    ├---╯  ┃   ┃   ┃   ┃   ┃   │   │    │   │  ╰---╮     

    ▏    │       ┃   ┃   ┃   ┃   ┃   │   │    │   │       │     

   ╰---╯╰----   ┃   ╯   ┃   ╰   ┃   ╰---╰╯  ╰---╯  ╰---╯     

Nein
Ja 2010-11-25

弄个最小/最大堆,复杂度是O(n lg k)吧

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

psaux
前行 2010-11-25

算法导论, 9.3 Selection in worst-case linear time

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

daryl
daryl 2010-11-25

算法导论,好像是第九章,线性时间内找出任何顺序统计量~

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-25

可以吧

【 在 Nein (Ja) 的大作中提到: 】

: 标  题: Re: 从一个未排序的列表,找第 k 个

: 发信站: 水木社区 (Thu Nov 25 00:40:38 2010), 站内

: 人家要求线性时间呢

: 【 在 Leimiaos (3WATER) 的大作中提到: 】

: : 标  题: Re: 从一个未排序的列表,找第 k 个

: : 发信站: 水木社区 (Thu Nov 25 00:10:17 2010), 站内

: :

: : 快速排序

: : 【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: : : 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: : : 谢谢

: :

: :

: : --

: :     ▏                                                                      

: :     ▏             ●                  ●                       ╭---╮     

: :     ▏    ╭---╮       ╭---┳---╮        ╭---╮    ╭---╮  │          

: :     ▏    ├---╯  ┃   ┃   ┃   ┃   ┃   │   │    │   │  ╰---╮     

: :     ▏    │       ┃   ┃   ┃   ┃   ┃   │   │    │   │       │     

: :    ╰---╯╰----   ┃   ╯   ┃   ╰   ┃   ╰---╰╯  ╰---╯  ╰---╯     

: :

: :

: --

kkw2008
kkw 2010-11-25

这个应该是用冒泡排序吧。时间复杂度是O(n)。

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

Nein
Ja 2010-11-25

how to?

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 标  题: Re: 从一个未排序的列表,找第 k 个

: 发信站: 水木社区 (Thu Nov 25 08:01:19 2010), 站内

: 可以吧

: 【 在 Nein (Ja) 的大作中提到: 】

: : 标  题: Re: 从一个未排序的列表,找第 k 个

: : 发信站: 水木社区 (Thu Nov 25 00:40:38 2010), 站内

: :

: : 人家要求线性时间呢

: :

: : 【 在 Leimiaos (3WATER) 的大作中提到: 】

: : : 标  题: Re: 从一个未排序的列表,找第 k 个

: : : 发信站: 水木社区 (Thu Nov 25 00:10:17 2010), 站内

: : :

: : : 快速排序

: : : 【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: : : : 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: : : : 谢谢

: : :

: : :

: : : --

: : :     ▏                                                                      

: : :     ▏             ●                  ●                       ╭---╮     

: : :     ▏    ╭---╮       ╭---┳---╮        ╭---╮    ╭---╮  │          

: : :     ▏    ├---╯  ┃   ┃   ┃   ┃   ┃   │   │    │   │  ╰---╮     

: : :     ▏    │       ┃   ┃   ┃   ┃   ┃   │   │    │   │       │     

: : :    ╰---╯╰----   ┃   ╯   ┃   ╰   ┃   ╰---╰╯  ╰---╯  ╰---╯     

: : :

: : :

: :

: :

: : --

: :

: --

: 秋风清,秋月明,

: 落叶聚还散,寒鸦栖复惊。

: 相思相见知何日,此时此夜难为情。

: 很有意义啊,好好活就是为了做有意义的事,有意义的事就是好好活。

Nein
Ja 2010-11-25

冒泡都开始了

【 在 kkw2008 (kkw) 的大作中提到: 】

: 这个应该是用冒泡排序吧。时间复杂度是O(n)。

SirFang
珍爱自己,珍爱爱人,珍爱所有人 2010-11-25

类似快排的partition, 每次partition后在剩下的一个区间内再查找,所以是O(n)的。

for exp:   5,4,2,1,7,6,8,   --> 查找4大数

(1)  Random pivot:  6

则:  partition 产生:  (5,4,2,1) 6 (7,8)

左边有4个元素, 因此6是第5大.

继续在左边找第4大数

(2)  Random pivot 2

则: (1) 2 (5,4)

2是第二大,在右边(5,4)里找第2大元素

T(n) = T(n/2) + O(n)  --> T(n) = O(n)

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

autohawk
凹凸霍克 2010-11-25

快排的变种,直排一半,复杂度就是线性了

【 在 Nein (Ja) 的大作中提到: 】

: 人家要求线性时间呢

GMingZBD
GMingZBD 2010-11-25

你这题目有点歧义。例如数列 2,3,1,5,4,4,5,找第3大的数

(1)如果是单纯的找按从大到小排序第k个元素,线性时间算法为:找第K个,那就换算成每次都找 最大的 那个 数,跟冒泡每趟起泡一样,只是不用交换数据,找K次,标记这趟比较找出最大值的索引。不过,第K次找最大数时,不要去比较前K-1 次找出的索引号。复杂度o(n).   找出的第3大的数是4.

【 在 autohawk (霍克) 的大作中提到: 】

: 快排的变种,直排一半,复杂度就是线性了

GMingZBD
GMingZBD 2010-11-25

(2)如果是找第k大的元素,不包括重复值的比较,线性时间算法为:找第K个,那就换算成每次都找 最大的 那个 数,跟冒泡每趟起泡一样,只是不用交换数据,找K次,标记这趟比较找出最大值。不过,第K次找最大数时,不要去比较前K-1 次找出的值。复杂度o(n).   找出的第3大的数是3.

GMingZBD
GMingZBD 2010-11-25

两种算法的区别就是 每次 找 最大 值 标记的是 索引号  还是 值。

当K<n/2时,按上面的找第K大,当K>n/2时,按上面的算法,找第n-k小的

这种算法 空间复杂度 和时间复杂度 都 最优了 .........,不可能还有更优的吧?

akat
阿卡 2010-11-25

复杂度和 K 有关系吧。

【 在 SirFang (珍爱自己,珍爱爱人,珍爱所有人) 的大作中提到: 】

: 类似快排的partition, 每次partition后在剩下的一个区间内再查找,所以是O(n)的。

: for exp:   5,4,2,1,7,6,8,   --> 查找4大数

: (1)  Random pivot:  6

: ...................

galoisrain
up|running |谁愿意错过年少轻狂 2010-11-25

查找中位数算法

其实就是快排的第一步

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

flagman
提琴协奏 2010-11-25

可以参考stl中的第n个大小元素的部分排序,

http://www.sgi.com/tech/stl/nth_element.html

复杂度是线性的。

【 在 lzcgsong (lzcgsong) 的大作中提到: 】

: 线形时间,从任意一个列表里,找出第 k 个最大或最小元素。

: 谢谢

RoBa269
弱吧 2010-11-25

这不是线性时间,在这里你不应该把k看作常数

【 在 GMingZBD (GMingZBD) 的大作中提到: 】

: 你这题目有点歧义。例如数列 2,3,1,5,4,4,5,找第3大的数

: (1)如果是单纯的找按从大到小排序第k个元素,线性时间算法为:找第K个,那就换算成每次都找 最大的 那个 数,跟冒泡每趟起泡一样,只是不用交换数据,找K次,标记这趟比较找出最大值的索引。不过,第K次找最大数时,不要去比较前K-1 次找出的索引号。复杂度o(n).   找

Leimiaos
3WATER 2010-11-25

是线性时间,每次处理分治的一段

【 在 Nein (Ja) 的大作中提到: 】

: 人家要求线性时间呢