国产精品天干天干,亚洲毛片在线,日韩gay小鲜肉啪啪18禁,女同Gay自慰喷水

歡迎光臨散文網(wǎng) 會(huì)員登陸 & 注冊(cè)

算法:隨機(jī)數(shù)索引

2022-05-17 09:58 作者:做架構(gòu)師不做框架師  | 我要投稿



題目

給你一個(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”,全部都是干貨。


算法:隨機(jī)數(shù)索引的評(píng)論 (共 條)

分享到微博請(qǐng)遵守國(guó)家法律
那曲县| 海林市| 历史| 大余县| 凤凰县| 尚志市| 吉木萨尔县| 凤凰县| 高淳县| 陵水| 文成县| 镇远县| 太保市| 商城县| 岗巴县| 孟村| 铜梁县| 中方县| 清新县| 彭泽县| 岐山县| 贡觉县| 东丰县| 新沂市| 平邑县| 景东| 哈巴河县| 额济纳旗| 竹山县| 武川县| 博客| 千阳县| 剑阁县| 务川| 怀集县| 靖安县| 新宾| 泰兴市| 广丰县| 吉首市| 阿坝|