成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode384. Shuffle an Array

cooxer / 1770人閱讀

摘要：題目要求實現(xiàn)和方法，分別能夠完成數(shù)組的隨機打亂和還原。隨機打亂即該數(shù)組中元素的所有排列組合結(jié)果都能夠以等比例的概率輸出。下面解釋一下證明，即為何每個該結(jié)果是等概率的排列組合結(jié)果。

題目要求 
Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

實現(xiàn)shuffle和reset方法，分別能夠完成數(shù)組的隨機打亂和還原。隨機打亂即該數(shù)組中元素的所有排列組合結(jié)果都能夠以等比例的概率輸出。

思路和代碼

直觀的思路來說，我們會將數(shù)組復(fù)制一份，并根據(jù)數(shù)組的長度來生成隨機數(shù)，并獲得該隨機數(shù)下標(biāo)上的值放在新的位置上。本文將詳細(xì)講解一下網(wǎng)上的另一種解法，即Fisher–Yates算法，該算法能夠用O(n)的時間隨機打亂一個數(shù)組。

該算法的步驟如下：

從數(shù)組中隨機選擇一個數(shù)字，與數(shù)組最后一個數(shù)字交換

從前n-1個元素中隨機選擇一個數(shù)字，與第n-1個數(shù)字交換

從前n-2個元素中隨機選擇一個數(shù)字，與第n-2個數(shù)字交換...

重復(fù)以上步驟，直到數(shù)組第一個元素。

下面解釋一下證明，即為何每個該結(jié)果是等概率的排列組合結(jié)果。

第一步操作，對于數(shù)組中所有的元素，均有1/n的概率交換到最后一個位置上

第二步操作可以分為兩種場景。

場景一：選中進行交換的元素為之前的最后一個元素，則該元素被選中的概率等于上一回合中該元素被交換到別的位置的概率乘以在當(dāng)前n-1個元素中被選中的概率，即((n-1)/n) * (1/n-1) = 1/n

場景二：選中進行交換的元素為其余的n-1個元素，則該元素被選中的概率等于上一回合中該元素沒被選中交換到最后一個位置的概率乘以在當(dāng)前n-1個元素中被選中的概率，即((n-1)/n * (1/n-1)) = 1/n

第三步操作可以分為三種場景：

場景一：選中進行交換的元素為最后一個元素，則該元素被選中的概率等于該元素被交換到前面n-2個元素的概率乘以該元素在當(dāng)前n-1個元素中被選中的概率。該元素沒有被交換到前面n-2個元素只有兩種可能，即位于原來的位置，或是被交換到倒數(shù)第二個位置，因此交換到前面n-2個元素的概率為(1 - 1/n - (n-1)/n * 1 / (n-1)) = (n-2) / n , 因此最終概率為(n-2)/n * 1/(n-2) = 1/n

場景二：選中進行交換的元素為倒數(shù)第二個元素，則該元素被選中的概率等于該元素被交換到前面n-2個元素的概率乘以該元素在當(dāng)前n-2個元素中被選中的概率。該元素沒有被交換到前面n-2個元素只有兩種可能，即該元素被交換至最后一個元素，或是依然位于原來的位置，因此交換到前面n-2個元素的概率為(1 - 1/n - (n-1)/n * 1 / (n-1)) = (n-2) / n, 因此最終概率為(n-2)/n * 1/(n-2) = 1/n

場景三：選中進行交換的元素為剩余的其他元素，則該元素被選中的概率沒有被交換到最后兩個位置上，最終概率也可以計算出來為1/n

綜上，這種方法能夠保證每一個元素可以等概率出現(xiàn)在任何位置上。代碼如下：

    private int[] nums;
    private Random random;
    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return this.nums;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        if(nums == null) return null;
        int[] result = nums.clone();
        for(int j = 1; j < result.length; j++) {
            int i = random.nextInt(j + 1);
            swap(result, i, j);
        }
        return result;
    }
    
    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/74774.html

相關(guān)文章

  • [LeetCode] 384. Shuffle an Array

    Problem Shuffle a set of numbers without duplicates. Example: // Init an array with set 1, 2, and 3.int[] nums = {1,2,3};Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return...

    Joyven 評論0 收藏0

  • [LeetCode] Shuffle an Array

    Problem Shuffle a set of numbers without duplicates. Example // Init an array with set 1, 2, and 3.int[] nums = {1,2,3};Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return ...

    Baaaan 評論0 收藏0

  • GTAV智能駕駛源碼詳解（二）——Train the AlexNet

    摘要：智能駕駛源碼詳解二模型簡介本使用進行圖像分類前進左轉(zhuǎn)右轉(zhuǎn)。其性能超群，在年圖像識別比賽上展露頭角，是當(dāng)時的冠軍，由團隊開發(fā)，領(lǐng)頭人物為教父。 GTAV智能駕駛源碼詳解（二）——Train the AlexNet 模型簡介： 本AI（ScooterV2）使用AlexNet進行圖像分類（前進、左轉(zhuǎn)、右轉(zhuǎn)）。Alexnet是一個經(jīng)典的卷積神經(jīng)網(wǎng)絡(luò)，有5個卷積層，其后為3個全連接層，最后的輸出...

    jayzou 評論0 收藏0

  • 也談前端面試常見問題之『數(shù)組亂序』

    摘要：看完部分的源碼，首先迫不及待想跟大家分享的正是本文主題數(shù)組亂序。這是一道經(jīng)典的前端面試題，給你一個數(shù)組，將其打亂，返回新的數(shù)組，即為數(shù)組亂序，也稱為洗牌問題。關(guān)于數(shù)組亂序，正確的解法應(yīng)該是，復(fù)雜度。 前言 終于可以開始 Collection Functions 部分了。 可能有的童鞋是第一次看樓主的系列文章，這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時候，學(xué)到...

    tracy 評論0 收藏0

  • JDK Collections.shuffle(List<?> list, Random

    摘要：的源碼如下一首先是判斷要打亂的的屬性的和是否實現(xiàn)接口如果的小于或者實現(xiàn)了接口，則直接交換內(nèi)元素的位置。以上內(nèi)容如有不正確的地方，歡迎支持。 jdk的源碼如下 public static void shuffle(List list, Random rnd) { int size = list.size(); if (size < SHUFFLE_THRE...

    Aomine 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<