成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

[Algo] Constant Time Random Picker 獲取集合內(nèi)隨機(jī)元素

calx / 1321人閱讀

摘要：但是這功能有要求我們必須保持內(nèi)容的有序，這樣我們才能通過(guò)隨機(jī)數(shù)的方法得到隨機(jī)的某個(gè)元素。取得隨機(jī)數(shù)的話，則是在當(dāng)前數(shù)組有效范圍內(nèi)取隨機(jī)數(shù)就行了。

Constant Time Random Picker 
設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持O(1)時(shí)間的查詢，增加，刪除，和得到其中隨機(jī)元素的操作，可以認(rèn)為其中的元素是數(shù)字。
哈希表數(shù)組 復(fù)雜度

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

思路

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

代碼 
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){
        // 將要?jiǎng)h的數(shù)和最后一個(gè)交換
        int idx = map.get(key);
        int tmp = arr.get(length - 1);
        arr.set(length - 1, key);
        arr.set(idx, tmp);
        // 更新元素和下標(biāo)的對(duì)應(yīng)關(guān)系
        map.put(tmp, idx);
        length--;
    }
    
    public int getRandom(){
        return arr.get(r.nextInt(length));
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/66175.html

相關(guān)文章

  • 基于K-means 切割多邊形 JAVA實(shí)現(xiàn)

    摘要：基于切割多邊形實(shí)現(xiàn)思路初稿詳見(jiàn)多邊形等分依賴實(shí)現(xiàn)實(shí)現(xiàn)過(guò)程結(jié)果類(lèi)泰森多邊形平分多邊形結(jié)果原始平面隨機(jī)點(diǎn)集合分組后組中心集合構(gòu)造泰森多邊形聚合類(lèi)聚合聚合總量數(shù)據(jù)集合簇族數(shù)量中 基于K-means 切割多邊形 JAVA實(shí)現(xiàn) 思路初稿詳見(jiàn)多邊形等分 依賴 geotools ekmeans org.locationtech.jts jts-co...

    haobowd 評(píng)論0 收藏0

  • surprise庫(kù)文檔翻譯

    摘要：默認(rèn)值為返回值，一個(gè)對(duì)象，包含了原生用戶原生項(xiàng)目真實(shí)評(píng)分預(yù)測(cè)評(píng)分可能對(duì)后面預(yù)測(cè)有用的一些其他的詳細(xì)信息在給定的測(cè)試集上測(cè)試算法，即估計(jì)給定測(cè)試集中的所有評(píng)分。 這里的格式并沒(méi)有做過(guò)多的處理，可參考于OneNote筆記鏈接 由于OneNote取消了單頁(yè)分享，如果需要請(qǐng)留下郵箱，我會(huì)郵件發(fā)送pdf版本，后續(xù)再解決這個(gè)問(wèn)題 推薦算法庫(kù)surprise安裝 pip install surp...

    JessYanCoding 評(píng)論0 收藏0

  • Tensorflow Python API 翻譯（constant_op）

    摘要：隨機(jī)數(shù)張量提供了一些函數(shù)，去幫助我們構(gòu)建隨機(jī)數(shù)張量。該值表示正態(tài)分布的均值。一個(gè)維的，或者一個(gè)數(shù)據(jù)類(lèi)型是的值，該值表示正態(tài)分布的標(biāo)準(zhǔn)偏差。解釋這個(gè)函數(shù)返回一個(gè)隨機(jī)數(shù)序列，數(shù)組里面的值按照均勻分布，數(shù)據(jù)范圍是。 作者：chen_h微信號(hào) & QQ：862251340微信公眾號(hào)：coderpai簡(jiǎn)書(shū)地址：https://www.jianshu.com/p/d05... 計(jì)劃現(xiàn)將 tens...

    godlong_X 評(píng)論0 收藏0

  • AOP實(shí)踐: Java利用注解和反射實(shí)現(xiàn)一個(gè)方便的函數(shù)性能測(cè)量工具

    摘要：實(shí)現(xiàn)先看實(shí)現(xiàn)之后的效果測(cè)試類(lèi)運(yùn)行輸出如下可以看到此時(shí)加了注解的和的運(yùn)行時(shí)間被統(tǒng)計(jì)了，而沒(méi)加的未被統(tǒng)計(jì)在內(nèi)。思路修改，在之前的中返回一個(gè)，儲(chǔ)存方法名耗時(shí)的鍵值結(jié)構(gòu)。然后降序排序返回一個(gè)。最后遍歷根據(jù)百分比求得各個(gè)方法的并輸出相關(guān)信息。 最初目的 在學(xué)習(xí)Java的集合類(lèi)時(shí)，有時(shí)候想要測(cè)試代碼塊的運(yùn)行時(shí)間，以比較不同算法數(shù)據(jù)結(jié)構(gòu)之間的性能差異。最簡(jiǎn)單的做法是在代碼塊的前后記錄時(shí)間戳，最后相減...

    zhangke3016 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<