題目

給你一個(gè)可能含有?重復(fù)元素?的整數(shù)數(shù)組?nums?，請(qǐng)你隨機(jī)輸出給定的目標(biāo)數(shù)字?target?的索引。你可以假設(shè)給定的數(shù)字一定存在于數(shù)組中。

實(shí)現(xiàn)?Solution?類

• Solution(int[]?nums)?用數(shù)組?nums?初始化對(duì)象。

• int?pick(int?target)?從?nums?中選出一個(gè)滿足?nums[i]?==?target?的隨機(jī)索引?i?。如果存在多個(gè)有效的索引，則每個(gè)索引的返回概率應(yīng)當(dāng)相等。

?測(cè)試用例

• 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)。對(duì)于?pick?操作，我們可以從?pos?中取出?target?對(duì)應(yīng)的下標(biāo)列表，然后隨機(jī)選擇其中一個(gè)下標(biāo)并返回。

復(fù)雜度分析

• 時(shí)間復(fù)雜度：初始化為O(n)，pick?為?O(1)，其中?nn?是?nums?的長(zhǎng)度。

• 空間復(fù)雜度：O(n)。我們需要?O(n)?的空間存儲(chǔ)?n?個(gè)下標(biāo)。

方法二：水塘抽樣

如果數(shù)組以文件形式存儲(chǔ)（讀者可假設(shè)構(gòu)造函數(shù)傳入的是個(gè)文件路徑），且文件大小遠(yuǎn)超內(nèi)存大小，我們是無(wú)法通過讀文件的方式，將所有下標(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?的長(zhǎng)度。

• 空間復(fù)雜度：O(1)。我們只需要常數(shù)的空間保存若干變量。

寫在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。