[数据结构与算法]【无标题】

每日一题 384.打乱数组（洗牌算法，随机数，数组复制）

洗牌算法

这个题目是https://leetcode-cn.com/problems/shuffle-an-array/
算法介绍如下：我们可以在移除 \textit{waiting}waiting 的第 kk 个元素时，将第 kk 个元素与数组的最后 11 个元素交换，然后移除交换后数组的最后 11 个元素，这样我们只需要 O(1)O(1) 的时间复杂度即可完成移除第 kk 个元素的操作。此时，被移除的交换后数组的最后 11 个元素即为我们根据随机下标获取的元素。

在此基础上，我们也可以不移除最后 11 个元素，而直接将其作为乱序后的结果，并更新待乱序数组的长度，从而实现数组的原地乱序。因为我们不再需要从数组中移除元素，所以也可以将第 kk 个元素与第 11 个元素交换。

具体地，实现算法如下（来自leetcode官方题解）：

随机数使用

随机数的定义以及功能使用：

Random rand= new Random();
 int out1=rand.nextInt(100);//返回一个[0,100）的随机数
 //Math.random()是令系统随机选取大于等于 0.0 且小于 1.0 的伪随机 double 值
 int out2=(int)(Math.random()*100+1)//取[1,101)区间内的数

数组复制

数组复制的方法：

int nums[]=new int[]{0,1,2,3};
int copyNums[]=(int[])Arrays.copyOfRange(nums,0,nums.length);//第一个参数是待复制数组，第二个参数是复制的起始索引，第三个参数是复制的结束索引（这行代码把整个数组复制给了copyNums）

代码

这是综合上述写的代码：

class Solution {

    private int numbers[];
    private int shunums[];
    public Solution(int[] nums) {
        this.numbers=nums;
        this.shunums=Arrays.copyOfRange(nums,0,nums.length);
    }
    
    public int[] reset() {
        return numbers;

    }
    
    public int[] shuffle() {
        this.shunums=Arrays.copyOfRange(this.numbers,0,this.numbers.length);
        int n=this.shunums.length;
        Random rand = new Random();
        for(int i=0;i<n;i++){
            int tempindex=rand.nextInt(n-i);
            int tempnumber=this.shunums[tempindex];
            this.shunums[tempindex]=this.shunums[n-i-1];
            this.shunums[n-i-1]=tempnumber;
        }

        return this.shunums;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */