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

calx 發(fā)布于2019-08-14 16:16 / 1240人閱讀

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

Constant Time Random Picker

設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，支持O(1)時間的查詢，增加，刪除，和得到其中隨機元素的操作，可以認(rèn)為其中的元素是數(shù)字。

哈希表數(shù)組 復(fù)雜度

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

思路

要求O(1)時間查詢和刪除，則想到哈希表，其他的數(shù)據(jù)結(jié)構(gòu)都要遍歷一遍才行。但是getRandom這功能有要求我們必須保持內(nèi)容的有序，這樣我們才能通過隨機數(shù)的方法得到隨機的某個元素。這里我們可以用數(shù)組、鏈表或者樹保持有序，但是鏈表得到第n個元素要O(N)的時間，而樹也要logN時間，所以不適合，只有數(shù)組。用數(shù)組的技巧在于，數(shù)組只是保持一個順序，我們可以哈希表表示一個元素和其在數(shù)組中下標(biāo)的映射關(guān)系，保證我們的O(1)查詢。而對于刪除，我們需要維護一個length變量（用表的大小也行），然后每次刪除的時候把要刪的數(shù)和數(shù)組當(dāng)前標(biāo)記的“最后”一個元素交換，然后把大小減一，并更新哈希表。取得隨機數(shù)的話，則是在當(dāng)前數(shù)組有效范圍內(nèi)取隨機數(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){
        // 將要刪的數(shù)和最后一個交換
        int idx = map.get(key);
        int tmp = arr.get(length - 1);
        arr.set(length - 1, key);
        arr.set(idx, tmp);
        // 更新元素和下標(biāo)的對應(yīng)關(guān)系
        map.put(tmp, idx);
        length--;
    }
    
    public int getRandom(){
        return arr.get(r.nextInt(length));
    }
}