馬克M細胞隨機以相等的概率

給定的N×N板被設置爲0的所有小區，標記M（M < N×N個）細胞到1。M細胞應選擇從所有細胞以相同的概率。

E.g.在10x10板中標記30個單元，然後選擇單元的概率爲0.3。

我的想法是迭代的所有細胞，並在每個單元計算在範圍[1-100]的隨機數，所述細胞標記爲1，如果數量小於或等於30

採訪者是沒有這個解決方案印象深刻。任何好主意？（您可以使用任何語言）

2014-11-21 Lee

的解決方案，您建議將標記大約30個單元格。但是，面試官可能希望你標出恰好30個單元格。您可以將1到100之間的數字放入數組中並對數組進行洗牌。然後使用該數組作爲隨機數的來源，並且您的方法標記了恰好30個單元格。 – user3386109 2014-11-21 06:27:55

@candu我不認爲這是重複的，因爲2D映射方面，但鏈接是非常有用的。 – pjs 2014-11-22 00:34:38

@pjs二維結構根本不會進入解決方案。 – 2014-11-22 04:29:27

將70個零（NxN-M）和30個（M）放入一個向量中。 Shuffle the vector。迭代遍歷並通過i = k/10和j = k % 10將您的示例中的每個索引k映射到二維索引（更一般地使用N作爲除數）。

附錄

檢查出@ CANDU的鏈接後，我決定放棄這個方法一試。下面是在Ruby中實現：

require 'set' 

# implementation of Floyd's uniform subset algorithm for 
# values in the range [0,n). 
def generateMfromN(m, n) 
    s = Set.new 
    ((n-m)...n).each {|j| s.add?(rand(j+1)) || s.add(j)} 
    s.to_a 
end 

#initialize a 10x10 array of zeros 
a = Array.new(10) 
10.times {|i| a[i] = Array.new(10,0)} 

# create an array of 10 random indices between 0 and 99, 
# map each index to 2-d indices, and set the corresponing 
# element to 1. 
generateMfromN(10,100).each {|index| a[index/10][index%10] = 1} 

# show the results 
a.each {|v| puts v.to_s}

這樣產生的結果，如...

[0, 0, 0, 1, 0, 0, 0, 0, 0, 0] 
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1] 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 
[0, 0, 0, 0, 0, 1, 0, 0, 1, 0] 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

，似乎只需要O（M）爲弗洛伊德的算法工作，由於每個M的重複元素總是被添加到集合中。

如果M大於N * N/2，則使用1初始化數組，然後按照@btilly的建議，隨機放置零。

來源

2014-11-21 06:09:41 pjs

謝謝。我當時並不知道「洗牌」。這應該是一個很好的解決方案。 – Lee 2014-11-24 03:11:48

這可以在預期的運行時間O(m)完成。

首先讓我們來處理最多需要董事會一半的情況。所以m <= n*n/2。對於這種情況，我們可以繼續選擇隨機點和改變它們的值，扔掉，我們之前選擇，直到我們有m他們。拋棄下一個隨機選擇的概率不會超過一半，因此所需的隨機選擇的數量最差爲2 m = O(m)。

在這裏我們需要一半以上的電路板的情況下，這需要時間來O(m)每一個細胞翻轉到1，然後我們使用以前的解決方案，以找到n*n - m細胞轉變回0

來源

2014-11-21 07:38:17 btilly

謝謝。實際上，當我沒有找到更正確的解決方案時，面試官給我的提示與您的解決方案類似。 – Lee 2014-11-24 03:13:25

@李我並不感到驚訝。我提供的解決方案不具備有保證的性能，但具有最佳的平均性能。相比之下，你接受的那個運行時間爲'O（n）'，而在'm = O（n）'具有明顯更差的常量的情況下。如果我是面試官，並且我得到了這個解決方案，我會推動一個更好的解決方案。 – btilly 2014-11-24 17:54:24

你在開玩笑說，這比洗牌更好。事實上，情況更糟。隨着洗牌，你只需要進行m次交換。然後你可以停下來。你的方法至少有m個樣本，但可能更多。 – 2015-11-02 23:19:37

馬克M細胞隨機以相等的概率

回答

相關問題