不重復(fù)地隨機獲取List或者數(shù)據(jù)元素

為了方便仑荐,我就以list為例:

算法思路

  1. 第一種方法的思路是:用set存儲已經(jīng)取過的下標(biāo)荚坞,每次循環(huán)取的時候虎谢,判斷是否已經(jīng)取過
    如果已經(jīng)取過就跳過本次循環(huán)科展,一直到取num為止

這個方法不推薦使用,可能會發(fā)生死循環(huán)
如果每一次的數(shù)據(jù)值都是同一個堪旧,那么就是死循環(huán)了削葱,雖然概論極其低,但是不代表沒有

public static List getListUnique1(List sources, int num) {

        if (sources.size() <= num) {
            return sources;
        }

        // 復(fù)制一份淳梦,以免對原數(shù)據(jù)造成影響
        List _sources = new ArrayList(sources);

        List targetList = new ArrayList(num);
        Set<Integer> gotIndexs = new HashSet<>(num); // 以獲取的下標(biāo)
        Random random = new Random();
        while (gotIndexs.size() < num) {
            int i = random.nextInt(_sources.size());

            // 已經(jīng)獲取過了析砸,跳過本次循環(huán)
            if (gotIndexs.contains(i)) continue;

            // 如果沒有獲取過,則放入數(shù)據(jù)
            targetList.add(_sources.get(i));
            gotIndexs.add(i);

        }
        return targetList;
    }
  1. 第二種方法思路是:每一次循環(huán)取完數(shù)據(jù)后爆袍,從目標(biāo)list中移除本次取的數(shù)據(jù)首繁,list的大小也變小了,下一次循環(huán)產(chǎn)生的隨機數(shù)最大值也是list的size陨囊,所以不會發(fā)生越界問題弦疮。
public static List getListUnique2(List sources, int num) {

        if (sources.size() <= num) {
            return sources;
        }

        // 復(fù)制一份,以免對原數(shù)據(jù)造成影響
        List _sources = new ArrayList(sources);

        List targetList = new ArrayList(num);
        Random random = new Random();
        for (int k = 0; k < num; k++) {
            int i = random.nextInt(_sources.size());
            targetList.add(_sources.get(i));
            // 取完后蜘醋,從目標(biāo)list內(nèi)移除該數(shù)據(jù)
            _sources.remove(i);
        }
        return targetList;
    }
  1. 第三中方法思路:每一次循環(huán)取完數(shù)據(jù)后胁塞,把list size - k -1 的元素 放到本次取到的index位置,下次循環(huán)的隨機數(shù)最大值為list size - k
public static List getListUnique3(List sources, int num) {

        if (sources.size() <= num) {
            return sources;
        }

        // 復(fù)制一份压语,以免對原數(shù)據(jù)造成影響
        List _sources = new ArrayList(sources);

        List targetList = new ArrayList(num);
        Random random = new Random();
        for (int k = 0; k < num; k++) {
            int i = random.nextInt(_sources.size() - k);
            Object tmp = _sources.get(i);
            targetList.add(tmp);
            // 取完后啸罢,把list size - k 的元素 放到本次取到的index位置
            _sources.set(i, _sources.get(_sources.size() - k - 1));

        }
        return targetList;
    }

分析

  • 第一種方法,不推薦使用胎食,這里就不說了
  • 如果list的實現(xiàn)為ArrayList扰才,那么第三種方法會比第二種好,因為在list移除的時候厕怜,實際上發(fā)生的數(shù)組的復(fù)制衩匣,有興趣的可以了解ArrayList的實現(xiàn)蕾总。
  • 如果list的實現(xiàn)為LinkedList,那么第三種方法和第二種方法沒有太多的差別
  • 上面的算法實現(xiàn)還可以優(yōu)化琅捏,例如生百,不用復(fù)制一份原數(shù)據(jù),直接使用原數(shù)據(jù)的下標(biāo)形成新的List午绳,然后對下標(biāo)進行隨機取置侍,取完后在根據(jù)下標(biāo)去原list中取對應(yīng)的數(shù)據(jù)。
  • 上面只給了List的實現(xiàn)拦焚,那數(shù)組的實現(xiàn)呢蜡坊?方法有兩種:
  1. 最簡單的是把數(shù)組轉(zhuǎn)換為ArrayList,然后就一樣了
  2. 根據(jù)上面的思路赎败,用數(shù)組實現(xiàn)秕衙。

各位,如果你有什么更好的想法僵刮,也歡迎評論

附源碼


/**
 * 獲取不重復(fù)下標(biāo)的元素
 */
public class UniqueCollectionIndex {

    public static void main(String[] args) {

        int num = 6;

        List list1 = new ArrayList();
        // 放入A-Z做測試
        for (int i = 65; i < 91; i++) {
            list1.add((char) i);
        }

        System.out.println(getListUnique1(list1, num));
        System.out.println(getListUnique2(list1, num));
        System.out.println(getListUnique3(list1, num));
        
    }


    //***** list *******

    /**
     * <p style="color:red">不推薦使用据忘,可能會發(fā)生死循環(huán)</p>
     * 用set存儲已經(jīng)取過的下標(biāo),每次循環(huán)取的時候搞糕,判斷是否已經(jīng)取過
     * 如果已經(jīng)取過就跳過本次循環(huán)勇吊,一直到取num為止
     *
     * @param sources 目標(biāo)list
     * @param num     獲取元素的數(shù)量
     * @return 獲取的list
     */
    public static List getListUnique1(List sources, int num) {

        if (sources.size() <= num) {
            return sources;
        }

        // 復(fù)制一份,以免對原數(shù)據(jù)造成影響
        List _sources = new ArrayList(sources);

        List targetList = new ArrayList(num);
        Set<Integer> gotIndexs = new HashSet<>(num); // 以獲取的下標(biāo)
        Random random = new Random();
        while (gotIndexs.size() < num) {
            int i = random.nextInt(_sources.size());

            // 已經(jīng)獲取過了窍仰,跳過本次循環(huán)
            if (gotIndexs.contains(i)) continue;

            // 如果沒有獲取過汉规,則放入數(shù)據(jù)
            targetList.add(_sources.get(i));
            gotIndexs.add(i);

        }
        return targetList;
    }

    /**
     * 每一次循環(huán)取完數(shù)據(jù)后,從目標(biāo)list中移除本次取的數(shù)據(jù)
     *
     * @param sources 目標(biāo)list
     * @param num     獲取元素的數(shù)量
     * @return 獲取的list
     */
    public static List getListUnique2(List sources, int num) {

        if (sources.size() <= num) {
            return sources;
        }

        // 復(fù)制一份驹吮,以免對原數(shù)據(jù)造成影響
        List _sources = new ArrayList(sources);

        List targetList = new ArrayList(num);
        Random random = new Random();
        for (int k = 0; k < num; k++) {
            int i = random.nextInt(_sources.size());
            targetList.add(_sources.get(i));
            // 取完后针史,從目標(biāo)list內(nèi)移除該數(shù)據(jù)
            _sources.remove(i);
        }
        return targetList;
    }

    /**
     * 每一次循環(huán)取完數(shù)據(jù)后,把list size - k -1 的元素 放到本次取到的index位置碟狞,
     * 下次循環(huán)的隨機數(shù)最大值為list size - k
     *
     * @param sources 目標(biāo)list
     * @param num     獲取元素的數(shù)量
     * @return 獲取的list
     */
    public static List getListUnique3(List sources, int num) {

        if (sources.size() <= num) {
            return sources;
        }

        // 復(fù)制一份啄枕,以免對原數(shù)據(jù)造成影響
        List _sources = new ArrayList(sources);

        List targetList = new ArrayList(num);
        Random random = new Random();
        for (int k = 0; k < num; k++) {
            int i = random.nextInt(_sources.size() - k);
            Object tmp = _sources.get(i);
            targetList.add(tmp);
            // 取完后,把list size - k 的元素 放到本次取到的index位置
            _sources.set(i, _sources.get(_sources.size() - k - 1));

        }
        return targetList;
    }


}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末族沃,一起剝皮案震驚了整個濱河市频祝,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌竭业,老刑警劉巖智润,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異未辆,居然都是意外死亡,警方通過查閱死者的電腦和手機锯玛,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進店門咐柜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來兼蜈,“玉大人,你說我怎么就攤上這事拙友∥辏” “怎么了?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵遗契,是天一觀的道長辐棒。 經(jīng)常有香客問我,道長牍蜂,這世上最難降的妖魔是什么漾根? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任,我火速辦了婚禮鲫竞,結(jié)果婚禮上辐怕,老公的妹妹穿的比我還像新娘。我一直安慰自己从绘,他們只是感情好寄疏,可當(dāng)我...
    茶點故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著僵井,像睡著了一般陕截。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上批什,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天农曲,我揣著相機與錄音,去河邊找鬼渊季。 笑死朋蔫,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的却汉。 我是一名探鬼主播驯妄,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼合砂!你這毒婦竟也來了青扔?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤翩伪,失蹤者是張志新(化名)和其女友劉穎微猖,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體缘屹,經(jīng)...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡凛剥,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了轻姿。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片犁珠。...
    茶點故事閱讀 40,769評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡逻炊,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出犁享,到底是詐尸還是另有隱情余素,我是刑警寧澤,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布炊昆,位于F島的核電站桨吊,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏凤巨。R本人自食惡果不足惜视乐,卻給世界環(huán)境...
    茶點故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望磅甩。 院中可真熱鬧炊林,春花似錦、人聲如沸卷要。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽僧叉。三九已至奕枝,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間瓶堕,已是汗流浹背隘道。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留郎笆,地道東北人谭梗。 一個月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓,卻偏偏與公主長得像宛蚓,于是被迫代替她去往敵國和親激捏。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,781評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序:基本語法凄吏,類相關(guān)的語法远舅,內(nèi)部類的語法,繼承相關(guān)的語法痕钢,異常的語法图柏,線程的語...
    子非魚_t_閱讀 31,665評論 18 399
  • Java源碼研究之容器(1) 如何看源碼 很多時候我們看源碼, 看完了以后經(jīng)常也沒啥收獲, 有些地方看得懂, 有些...
    駱駝騎士閱讀 996評論 0 22
  • 在經(jīng)過一次沒有準(zhǔn)備的面試后,發(fā)現(xiàn)自己雖然寫了兩年的android代碼任连,基礎(chǔ)知識卻忘的差不多了蚤吹。這是程序員的大忌,沒...
    猿來如癡閱讀 2,849評論 3 10
  • 我在輸出力學(xué)院畢業(yè)了 ——我的收獲 2017.6.20第一次大課高效輸入法随抠,第一次聆聽阿秋的課距辆,分別從行動模式余佃、心...
    宏丫頭閱讀 262評論 0 0
  • 上一篇文章提到了rabbitMQ的體系結(jié)構(gòu)和一些核心概念暮刃,這篇文章就通過一個最簡單的Java版helloWorld...
    lsfire閱讀 268評論 0 0