関小君刷题记

题目大意：

打乱数组

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

示例:

// 以数字集合 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-解题思路分析/