线性时间查找中位数

aimisiyou

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

yuren008

做个对论坛有益的人。

aimisiyou

_$ ;;;求列表中第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
_$