找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 349|回复: 2

[研讨] 线性时间查找中位数

[复制链接]

已领礼包: 1857个

财富等级: 堆金积玉

发表于 2020-1-12 19:42:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
Consider the list below. We'd like to find the median.
l = [9,1,0,2,3,4,6,8,7,10,5]
len(l) == 11, so we're looking for the 6th smallest element
First, we must pick a pivot. We randomly select index 3.
The value at this index is 2.

Partitioning based on the pivot:
[1,0,2], [9,3,4,6,8,7,10,5]
We want the 6th element. 6-len(left) = 3, so we want
the third smallest element in the right array

We're now looking for third smallest element in the array below:
[9,3,4,6,8,7,10,5]
We pick an index at random to be our pivot.
We pick index 3, the value at which, l[3]=6

Partitioning based on the pivot:
[3,4,5,6] [9,7,10]
We want the 3rd smallest element, so we know it's the
3rd smallest element in the left array

We're now looking for the 3rd smallest in the array below:
[3,4,5,6]
We pick an index at random to be our pivot.
We pick index 1, the value at which, l[1]=4
Partitioning based on the pivot:
[3,4] [5,6]
We're looking for the item at index 3, so we know it's
the smallest in the right array.

We're now looking for the smallest element in the array below:
[5,6]

At this point, we can have a base case that chooses the larger
or smaller item based on the index.
We're looking for the smallest item, which is 5.
return 5
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 2230个

财富等级: 金玉满堂

发表于 2020-1-12 19:55:51 | 显示全部楼层
做个对论坛有益的人。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-24 16:11:30 | 显示全部楼层
_$ ;;;求列表中第K大的数
(defun f(lst k)
(defun rnd ()(*(rem (getvar "cputicks") 1e4) 1e-4))
(defun rnd_n (n)(fix (* n (rnd))))
(setq n (length lst) nk (rnd_n n))
(setq lst1 (vl-remove nil (mapcar '(lambda (x) (if  (> x (nth nk lst)) x nil)) lst)))
(setq lst2 (vl-remove nil (mapcar '(lambda (x) (if  (< x (nth nk lst)) x nil)) lst)))
(cond
   ((= (length lst1) (- k 1))  (setq va (nth nk lst)))
   ((> (length lst1) (- k 1))  (setq va (f lst1 k)))
   ((< (length lst1) (- k 1))  (setq va (f lst2 (- k (length lst1) 1))))
  )
)
(f '(9 7 5 3 1 8 6 4 2) 4)
F
6
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-29 09:39 , Processed in 0.338362 second(s), 31 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表