我可以比二進制搜索做得更好嗎？

我想根據百分比挑選卡片的頂部「範圍」。我有我的所有可能的2手牌在手的實力的順序在陣列組織，就像這樣：我可以比二進制搜索做得更好嗎？

AA, KK, AKsuited, QQ, AKoff-suit ...

我是已通過該卡數組的長度乘以採摘手的前10％這個百分比會給我數組中最後一張牌的索引。然後，我只想讓子數組的副本：

Arrays.copyOfRange(cardArray, 0, 16);

不過，我現在認識到，因爲有，比如說，王牌敬客，西裝更可能的組合，這是不正確 - 12個組合（即一套西裝的王牌和另一套西裝的國王）比組合，比如說，一對王牌 - 6種組合。

當我拿起手中的前10％，因此，我希望它可以根據手的前10％的比例的2個卡組合的總數 - 52選2 = 1326

我想我可以有一個整數數組，其中每個索引都保存了到該點爲止的所有組合的總數（每個索引將對應於原始數組中的一隻手）。因此，陣列的前幾個指數將是：

6, 12, 16, 22

因爲有AA的6種組合，KK的6種組合，AKsuited的4種組合，QQ的6種組合。

然後我可以做一個二進制搜索，它運行在BigOh（log n）時間。換句話說，我可以將組合的總數（1326）乘以百分比，搜索第一個低於或等於該數字的索引，並且這將是我需要的原始數組的索引。

我想知道是否有一種方法可以在常量時間內完成此操作？

來源

2011-12-22 Joe

由於1326不是那麼大的數字，爲什麼不簡單地預先創建所有的元組並將它們存儲在一個有序數組中呢？ – Groo 2011-12-22 14:06:57

你的意思是說我有一個長度爲1326的二維數組，在另一個維度中，它會有一個卡片範圍數組？因此，第一個索引將有一個「AA」陣列，最後一個索引將包含一個包含所有可能手的數組。這個數據結構通常如何在軟件中初始化？我使用Java，所以我可以將它作爲文字鍵入 - NO，在構造函數中以編程方式構造，並確保將該對象保持爲活動狀態，因此我只需要執行一次，或者從文件中讀取該計劃的開始。謝謝你的評論。 – Joe 2011-12-22 14:29:08

我正在考慮按順序排序的* all *組合的1維數組。從52張牌組中選擇兩張牌有1326種方式，因此只需創建所有組合並對其進行分類。 – Groo 2011-12-22 14:36:05

正如Groo建議的那樣，如果預計算和內存開銷允許，創建6個AA副本，6個KK副本等等並將它們存儲到排序數組中將會更有效。然後你可以在這個適當加權的列表上運行你的原始算法。

如果查詢數量很大，這是最好的。

否則，我不認爲你可以實現每個查詢的恆定時間。這是因爲查詢取決於整個頻率分佈。你不能僅僅關注元素的數量並確定它是否是正確的百分點。

來源

2011-12-22 14:20:14 tskuzzy

感謝您的回答。對，我認爲Groo意味着有一個二維數組，因爲我在他的評論下評論過。如果我使用1d解決方案，那麼結果是我有問題的答案，這個範圍內最差的手是什麼，但我仍然必須找出原始數組中的位置（最壞的情況是BigOh（n）因爲它沒有排序），所以我可以指定方法的參數來獲取子數組。但我很可能會錯過一些東西。 – Joe 2011-12-22 14:33:40

這裏Algorithm for picking thumbed-up items有過類似的討論，至於我的回答（基本上你想與你的卡列表做什麼），有人提出了一個具體的數據結構的評論，http://en.wikipedia.org/wiki/Fenwick_tree

此外，請確保您的數據結構能夠提供有效的訪問，例如，最高5％和15％之間的範圍（儘管如此，不是編碼相關的提示）。

來源

2011-12-23 18:49:12 Nicolas78

我可以比二進制搜索做得更好嗎？

回答

相關問題