X

LEETCODE 384. Shuffle an Array 解题思路分析

题目大意:

打乱数组

打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=384

解题思路分析:

本题需要实现两个方法,一个是打乱数组,一个是还原数组,因此我们需要在内存中保存两份数组对象,一个作为原始数组的备份,另一个用来打乱。

先看如何打乱数组。所谓打乱,意思就是原先每个位置上的数字会随机变换到其他位置,因此,我们需要循环数组的每一位,然后随机生成一个小于数组长度的数字来代表随机交换的位置,然后我们将当前数字与随机位置上的数字进行交换。循环完每一位的数字之后,也就随机交换了所有位上的数字,到达打乱数组的目的。

对于还原数组就相对简单很多,我们只要将打乱的数组更改为原数组即可。

实现代码:

int[] original; // 原始数组
int[] copy; // 拷贝数组,用于打乱
Random r = new Random(); // 随机
public Solution(int[] nums) {
    original = nums;
    copy=Arrays.copyOf(original,original.length);
}

/** Resets the array to its original configuration and return it. */public int[] reset() {
    // 将原始数组复制到copy数组
    copy=Arrays.copyOf(original,original.length);
    return copy;
}

/** Returns a random shuffling of the array. */public int[] shuffle() {
    if(copy.length==0) return copy;
    // 循环数组每一位
    for(int i=copy.length-1;i>=0;i--){
        // 当前位的值
        int current=copy[i];
        // 随机生成一个小于数组长度的下标
        int ir = r.nextInt(copy.length);
        // 交换当前位置与随机下标位置上的数字
        copy[i]=copy[ir];
        copy[ir]=current;
    }
    return copy;
}

本题解法执行时间为73ms。

Runtime: 73 ms, faster than 81.45% of Java online submissions for Shuffle an Array.

Memory Usage: 51.2 MB, less than 100.00% of Java online submissions for Shuffle an Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-384-shuffle-an-array-解题思路分析/
Categories: leetcode
kwantong:

View Comments (1)

  • I seriously love your site.. Excellent colors & theme. Did you create this web site yourself?
    Please reply back as I'm wanting to create
    my own personal site and would like to learn where you got this from or exactly what the theme is called.
    Cheers!