leetcode384. Shuffle an Array

cooxer 发布于2019-08-16 17:50 / 1718人阅读

摘要：题目要求实现和方法，分别能够完成数组的随机打乱和还原。随机打乱即该数组中元素的所有排列组合结果都能够以等比例的概率输出。下面解释一下证明，即为何每个该结果是等概率的排列组合结果。

题目要求

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();

实现shuffle和reset方法，分别能够完成数组的随机打乱和还原。随机打乱即该数组中元素的所有排列组合结果都能够以等比例的概率输出。

思路和代码

直观的思路来说，我们会将数组复制一份，并根据数组的长度来生成随机数，并获得该随机数下标上的值放在新的位置上。本文将详细讲解一下网上的另一种解法，即Fisher–Yates算法，该算法能够用O(n)的时间随机打乱一个数组。

该算法的步骤如下：

从数组中随机选择一个数字，与数组最后一个数字交换

从前n-1个元素中随机选择一个数字，与第n-1个数字交换

从前n-2个元素中随机选择一个数字，与第n-2个数字交换...

重复以上步骤，直到数组第一个元素。

下面解释一下证明，即为何每个该结果是等概率的排列组合结果。

第一步操作，对于数组中所有的元素，均有1/n的概率交换到最后一个位置上

第二步操作可以分为两种场景。

场景一：选中进行交换的元素为之前的最后一个元素，则该元素被选中的概率等于上一回合中该元素被交换到别的位置的概率乘以在当前n-1个元素中被选中的概率，即((n-1)/n) * (1/n-1) = 1/n

场景二：选中进行交换的元素为其余的n-1个元素，则该元素被选中的概率等于上一回合中该元素没被选中交换到最后一个位置的概率乘以在当前n-1个元素中被选中的概率，即((n-1)/n * (1/n-1)) = 1/n

第三步操作可以分为三种场景：

场景一：选中进行交换的元素为最后一个元素，则该元素被选中的概率等于该元素被交换到前面n-2个元素的概率乘以该元素在当前n-1个元素中被选中的概率。该元素没有被交换到前面n-2个元素只有两种可能，即位于原来的位置，或是被交换到倒数第二个位置，因此交换到前面n-2个元素的概率为(1 - 1/n - (n-1)/n * 1 / (n-1)) = (n-2) / n , 因此最终概率为(n-2)/n * 1/(n-2) = 1/n

场景二：选中进行交换的元素为倒数第二个元素，则该元素被选中的概率等于该元素被交换到前面n-2个元素的概率乘以该元素在当前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

综上，这种方法能够保证每一个元素可以等概率出现在任何位置上。代码如下：

    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;
    }

云服务器 GPU云服务器 Shuffle 服务器384一个月 str_shuffle Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74774.html

[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 2019-08-16 13:43 评论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 2019-08-15 15:46 评论0 收藏0
GTAV智能驾驶源码详解（二）——Train the AlexNet

摘要：智能驾驶源码详解二模型简介本使用进行图像分类前进左转右转。其性能超群，在年图像识别比赛上展露头角，是当时的冠军，由团队开发，领头人物为教父。 GTAV智能驾驶源码详解（二）——Train the AlexNet 模型简介：本AI（ScooterV2）使用AlexNet进行图像分类（前进、左转、右转）。Alexnet是一个经典的卷积神经网络，有5个卷积层，其后为3个全连接层，最后的输出...

jayzou 2019-07-31 11:00 评论0 收藏0
也谈前端面试常见问题之『数组乱序』

摘要：看完部分的源码，首先迫不及待想跟大家分享的正是本文主题数组乱序。这是一道经典的前端面试题，给你一个数组，将其打乱，返回新的数组，即为数组乱序，也称为洗牌问题。关于数组乱序，正确的解法应该是，复杂度。前言终于可以开始 Collection Functions 部分了。可能有的童鞋是第一次看楼主的系列文章，这里再做下简单的介绍。楼主在阅读 underscore.js 源码的时候，学到...

tracy 2019-08-19 18:42 评论0 收藏0
JDK Collections.shuffle(List<?> list, Random

摘要：的源码如下一首先是判断要打乱的的属性的和是否实现接口如果的小于或者实现了接口，则直接交换内元素的位置。以上内容如有不正确的地方，欢迎支持。 jdk的源码如下 public static void shuffle(List list, Random rnd) { int size = list.size(); if (size < SHUFFLE_THRE...

Aomine 2019-08-15 14:48 评论0 收藏0