算法或此數據結構

Question

有一個問題說： 給定一個數字n和n卡片，每張卡片上寫入一個數字 我們有骰子，k倍我們擲骰子，如果骰子顯示的數字是m，那麼我們必須劃掉其中一個可以劃分的數字m 困難在於劃痕數字應該在O（1）中完成

我找不到解決方案，可能是算法或需要特殊的數據結構

如果有人能幫我，我會變得開心:)

tnx！ :)

Answer 1

如果您知道卡上的所有數字都是唯一的，您可以創建一個數組並將該卡對象存儲在寫入數字索引的數組中。颳了一些會就做

cardArray[number].scratch() 

如果數量很大，你需要創建一個大陣，因此這將是更好地創建一個散列。

cards = {cardNumber:cardObject, ...} 
cards[cardNumber].scratch 

劃傷被m整除的所有數字創建的散列如下

dicemax = 6 
scratched = {number: false; ....} 
card.scratched? => return scratched[card.number % dicemax] 

你跟蹤哪個號碼正在使用的劃傷哈希滾動。所以抓他們將在O（1）中，只是重寫哈希的值。 檢查一張卡是否被劃傷，你得到卡上的號碼。然後看看它的數字是模子的最大值。如果這個數字在哈希中被劃傷，則卡被劃傷。