算法：隨機(jī)數(shù)索引
題目
給你一個(gè)可能含有 重復(fù)元素 的整數(shù)數(shù)組 nums ，請你隨機(jī)輸出給定的目標(biāo)數(shù)字 target 的索引。你可以假設(shè)給定的數(shù)字一定存在于數(shù)組中。
實(shí)現(xiàn) Solution 類
Solution(int[] nums) 用數(shù)組 nums 初始化對象。
int pick(int target) 從 nums 中選出一個(gè)滿足 nums[i] == target 的隨機(jī)索引 i 。如果存在多個(gè)有效的索引，則每個(gè)索引的返回概率應(yīng)當(dāng)相等。
測試用例
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // 隨機(jī)返回索引 2, 3 或者 4 之一。每個(gè)索引的返回概率應(yīng)該相等。
solution.pick(1); // 返回 0 。因?yàn)橹挥?nums[0] 等于 1 。
solution.pick(3); // 隨機(jī)返回索引 2, 3 或者 4 之一。每個(gè)索引的返回概率應(yīng)該相等。
方法一：哈希表
如果不考慮數(shù)組的大小，我們可以在構(gòu)造函數(shù)中，用一個(gè)哈希表 pos 記錄 nums 中相同元素的下標(biāo)。
對于 pick 操作，我們可以從 pos 中取出 target 對應(yīng)的下標(biāo)列表，然后隨機(jī)選擇其中一個(gè)下標(biāo)并返回。
復(fù)雜度分析
時(shí)間復(fù)雜度：初始化為O(n)，pick 為 O(1)，其中 nn 是 nums 的長度。
空間復(fù)雜度：O(n)。我們需要 O(n) 的空間存儲(chǔ) n 個(gè)下標(biāo)。
方法二：水塘抽樣
如果數(shù)組以文件形式存儲(chǔ)（讀者可假設(shè)構(gòu)造函數(shù)傳入的是個(gè)文件路徑），且文件大小遠(yuǎn)超內(nèi)存大小，我們是無法通過讀文件的方式，將所有下標(biāo)保存在內(nèi)存中的，因此需要找到一種空間復(fù)雜度更低的算法。
我們可以設(shè)計(jì)如下算法實(shí)現(xiàn) pick 操作：
遍歷 nums，當(dāng)我們第 ii 次遇到值為 target 的元素時(shí)，隨機(jī)選擇區(qū)間 [0,i) 內(nèi)地一個(gè)整數(shù)，如果其等于 0，則將返回值置為該元素的下標(biāo)，否則返回值不變。
復(fù)雜度分析
時(shí)間復(fù)雜度：初始化為 O(1)，pick 為 O(n)，其中 n 是 nums 的長度。
空間復(fù)雜度：O(1)。我們只需要在常數(shù)的空間保存若干變量。
寫在最后
本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！
好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。
