1. 描述

• 給定一個包含 [0，n) 中不重復整數的黑名單 blacklist ，寫一個函數從 [0, n) 中返回一個不在 blacklist 中的隨機整數。
  對它進行優化使其盡量少的調用Math.random()。

• You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely returned.
  Optimize your algorithm such that it minimizes the call to the built-in random function of your language.
  Implement the Solution class:

  • Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.
  • int pick() Returns a random integer in the range [0, n - 1] and not in blacklist. All the possible integers should be equally likely returned.

2. 分析

• 第一想法：每次生成隨機數都判斷是否在黑名單內，在則重新生成，但這樣的設計不符合盡量少調用random()的要求。
• 大致思路：那么如何做到盡量少的調用random()呢？如果生成的隨機數一定不在黑名單中，則每次pick()只用調用一次random()，這就需要我們把[0, n)看成一個數組，把黑名單中的數移到末尾，由于知道黑名單中有多少個數，我們就可以知道應該生成零到幾的隨機數了。
• 具體思路：將黑名單中的數移到末尾如何實現呢？其實數組[0, n)相當于最終被分成了定長的兩塊，前一部分為白名單，后一部分為黑名單。正常來說想法是遍歷原數組，如果在黑名單中，則把數交換到末尾。但這樣做有兩個問題：一是如何快速判斷當前數在不在黑名單中，二是需要確定交換的數不在黑名單中。
• 問題一的本質是如何快速查詢一個數在不在一個集合中，可以通過把黑名單中的數存進哈希表來來解決。第二個問題在創建哈希表后也得到解決。同時在建立了哈希表后，就不再需要遍歷數組了，只需要在哈希表中進行查找，如果哈希表中的數在數組的黑名單區間，則不用移動。
• 整體算法為：
  • 把0~N分成兩段，前半段為白名單，后半段為黑名單：先建立一個存有所有黑名單數的map便于查詢，再將在前半段范圍內的黑名單數與在后半段的白名單數建立映射（作為鍵值對加入map），這樣相當于前半段都是白名單數
    
  • 取隨機數：只用在前半段內取隨機數，若取到了黑名單數，則去map中取對應的白名單數作為返回值即可

3. 代碼

class Solution {Random random;Map<Integer, Integer> blackmap;int thre;public Solution(int n, int[] blacklist) {random = new Random();blackmap = new HashMap<>();// 將blacklist中的數存入hashmap，便于查詢一個數是否在blacklist中for(int b: blacklist){blackmap.put(b, 66);}thre = n - blacklist.length;int last = n - 1;for(int b: blacklist){if(b >= thre) continue;while(blackmap.containsKey(last)){last--;}// 在hashmap中存入替換的值blackmap.put(b, last);// 存值后last要記得--，不然下一個黑名單中的數依然會用這個值替換last--;}}public int pick() {int rand = random.nextInt(thre);if(blackmap.containsKey(rand)){return blackmap.get(rand);} else {return rand;}} }

總結

以上是生活随笔為你收集整理的710. Random Pick with Blacklist 黑名单中的随机数（Hard）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。