[Algo] Constant Time Random Picker 獲取集合內隨機元素

calx 發布于2019-08-14 16:16 / 1247人閱讀

摘要：但是這功能有要求我們必須保持內容的有序，這樣我們才能通過隨機數的方法得到隨機的某個元素。取得隨機數的話，則是在當前數組有效范圍內取隨機數就行了。

Constant Time Random Picker

設計一個數據結構，支持O(1)時間的查詢，增加，刪除，和得到其中隨機元素的操作，可以認為其中的元素是數字。

哈希表數組 復雜度

時間 O(1) 空間 O(N)

思路

要求O(1)時間查詢和刪除，則想到哈希表，其他的數據結構都要遍歷一遍才行。但是getRandom這功能有要求我們必須保持內容的有序，這樣我們才能通過隨機數的方法得到隨機的某個元素。這里我們可以用數組、鏈表或者樹保持有序，但是鏈表得到第n個元素要O(N)的時間，而樹也要logN時間，所以不適合，只有數組。用數組的技巧在于，數組只是保持一個順序，我們可以哈希表表示一個元素和其在數組中下標的映射關系，保證我們的O(1)查詢。而對于刪除，我們需要維護一個length變量（用表的大小也行），然后每次刪除的時候把要刪的數和數組當前標記的“最后”一個元素交換，然后把大小減一，并更新哈希表。取得隨機數的話，則是在當前數組有效范圍內取隨機數就行了。

代碼

public class RandomPicker {
    Random r;
    ArrayList arr;
    HashMap map;
    int length;
    
    public RandomPicker(){
        this.r = new Random();
        this.arr = new ArrayList<>();
        this.map = new HashMap<>();
        this.length = 0;
    }
    
    public void add(int key){
        arr.add(length, key);
        map.put(key, length);
        length++;
    }
    
    public void delete(int key){
        // 將要刪的數和最后一個交換
        int idx = map.get(key);
        int tmp = arr.get(length - 1);
        arr.set(length - 1, key);
        arr.set(idx, tmp);
        // 更新元素和下標的對應關系
        map.put(tmp, idx);
        length--;
    }
    
    public int getRandom(){
        return arr.get(r.nextInt(length));
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66175.html

基于K-means 切割多邊形 JAVA實現

摘要：基于切割多邊形實現思路初稿詳見多邊形等分依賴實現實現過程結果類泰森多邊形平分多邊形結果原始平面隨機點集合分組后組中心集合構造泰森多邊形聚合類聚合聚合總量數據集合簇族數量中基于K-means 切割多邊形 JAVA實現思路初稿詳見多邊形等分依賴 geotools ekmeans org.locationtech.jts jts-co...

haobowd 2019-08-16 14:30 評論0 收藏0
surprise庫文檔翻譯

摘要：默認值為返回值，一個對象，包含了原生用戶原生項目真實評分預測評分可能對后面預測有用的一些其他的詳細信息在給定的測試集上測試算法，即估計給定測試集中的所有評分。這里的格式并沒有做過多的處理，可參考于OneNote筆記鏈接由于OneNote取消了單頁分享，如果需要請留下郵箱，我會郵件發送pdf版本，后續再解決這個問題推薦算法庫surprise安裝 pip install surp...

JessYanCoding 2019-07-31 10:25 評論0 收藏0
Tensorflow Python API 翻譯（constant_op）

摘要：隨機數張量提供了一些函數，去幫助我們構建隨機數張量。該值表示正態分布的均值。一個維的，或者一個數據類型是的值，該值表示正態分布的標準偏差。解釋這個函數返回一個隨機數序列，數組里面的值按照均勻分布，數據范圍是。作者：chen_h微信號 & QQ：862251340微信公眾號：coderpai簡書地址：https://www.jianshu.com/p/d05... 計劃現將 tens...

godlong_X 2019-07-30 15:25 評論0 收藏0
AOP實踐: Java利用注解和反射實現一個方便的函數性能測量工具

摘要：實現先看實現之后的效果測試類運行輸出如下可以看到此時加了注解的和的運行時間被統計了，而沒加的未被統計在內。思路修改，在之前的中返回一個，儲存方法名耗時的鍵值結構。然后降序排序返回一個。最后遍歷根據百分比求得各個方法的并輸出相關信息。最初目的在學習Java的集合類時，有時候想要測試代碼塊的運行時間，以比較不同算法數據結構之間的性能差異。最簡單的做法是在代碼塊的前后記錄時間戳，最后相減...

zhangke3016 2019-08-14 14:55 評論0 收藏0