1樓：
一,在剩餘r個裡面抽取s個,使用s/r選取下乙個.可以證明每個選擇的概率都是s/r.
1.第n=1個選擇概率是s/r.
2.當n>1時，當前樣本選擇的概率為前乙個選中的概率乘以選中當前的概率s/r*(s-1)/(r-1)加上前乙個沒選中乘以選中當前的概率(1-s/r)*s/(r-1). 二者相加之和為s/r.
故每個樣本選中的概率均為s/r.
二, while(set.size() < 2012) set.insert(rand(0,100000);
三, Fisher-yates shuffling 前2012個
2樓：王東嶽
for i: 1 ~ 2012
x = random(0~100000-i);
print a[x];
a[x] = a[10000-i];
3樓：MaskRay
Ruby
# in-place Fisher-Yates-esquedefreservoir_sample(n,k)a
={}k.
timesa.
values_at*k
.times
endp
reservoir_sample5,3
4樓：
來乙個真正的民工演算法吧：
先取1-10w的隨機數2012個，然後用二叉樹排序並檢驗是否有重複，假設有m個重複的話就重新抽取m個，繼續排序。只要不是運氣太差的話基本可以在O(klogk)內搞定吧...
5樓：櫻桃小財主
foriin
range
(2012
):swap(a
[i],a
([random(i
,100000
)])取前2012個就好
6樓：
思考一下random shuffle的過程swap(a
[i],
a[rand(n
-i)+
i])foriin
0...
n這個過程給我們什麼啟發呢...
swap左邊這個一旦定下來就不會再改變了.
再回想一下直接用random shuffle的時候我們是怎麼做的?
把random shuffle的前2012個數字取出來..
這提醒我們, 根本就不用把整個陣列全部打亂.
只需要對前個位置做這個操作就行了...
至於交換到後面的數字怎麼處理, 隨便用個map塞一下就可以了, 複雜度是, 是要取出的數的個數, 考慮到比小得多, 這樣會更快, 我想在實際的使用中也會更為常見...
一道IT筆試題？
貓咪 1 9是揹包問題 f x min f x k i 1 f x k i min f x 1,f x k i 超過10時f x min f x 10 1,f x 9 3 而fabs f x f x 1 1，所以這裡應該是貪心。int f x 此為亂答 既然是按鍵，按太多肯定不爽。把1 10000溫...
一道阿里筆試題，思路應該是怎樣？
納尼思密達 import com.alibaba.fastjson.JSONObject public class Test int k 1,i arr.length k j 0 int tmp arr i while j arr.length j handle arr,i,j,i,tmp i ar...
一道華為的筆試題，講一下思路？
陳肖 今天剛好刷到這道題，總共兩種變種，可以用DP完成。Edit Distance Delete Operation for Two Strings Coldwings DP 最短路均可解。如果不知道怎麼寫O N 2 的DP優化，很簡單啊，把問題轉成最短路上SPFA即可。以數對 I,J 視為節點，表...