LeetCode日常之动态规划：384 打乱数组

题目信息

题目地址：leetcode-cn.com/problems/sh…

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class: Solution(int[] nums) 使用整数数组 nums 初始化对象 int[] reset() 重设数组到它的初始状态并返回 int[] shuffle() 返回数组随机打乱后的结果

示例：

 输入
 ["Solution", "shuffle", "reset", "shuffle"]
 [[[1, 2, 3]], [], [], []]
 输出
 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释

 Solution solution = new Solution([1, 2, 3]);
 solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
 solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
 solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

1 <= nums.length <= 200 -106 <= nums[i] <= 106 nums 中的所有元素都是 唯一的 最多可以调用 5 * 104 次 reset 和 shuffle

解法一：暴力

题目意思是让我们实现一个类，它测试就会创建对象并且调用打乱方法与重置方法。既然有重置的话打乱的修改不是在原数组上进行。第一是新数组第二是随机位置。 那我们就可以使用ArrayList与Random来实现

代码如下

 class Solution {
     // 原数组、打乱返回数组、随机数
     private int[] nums;
     private int[] result;
     private Random rand = new Random();
     // 构造器初始化原数组与打乱数组的空间
     public Solution(int[] nums) {
         this.nums = nums;
         result = new int[nums.length];
     }
     // 重置方法：即返回原数组
     public int[] reset() {
         return nums;
     }
     // 打乱方法：arrayList随机取[0,size)
     public int[] shuffle() {
         //获取原数组的arrayList
         List<Integer> arrayList = getArrayList();
         for (int i = 0; i < nums.length; i++) {
             int index = rand.nextInt(arrayList.size());
             result[i] = arrayList.get(index);
             arrayList.remove(index);
         }
         return result;
     }
     // 获取List方法
     private List<Integer> getArrayList() {
         List<Integer> arrayList = new ArrayList<Integer>();
         for (int i = 0; i < nums.length; i++) {
             arrayList.add(nums[i]);
         }
         return arrayList;
     }
 }

时间复杂度：最差有(51024) (n/2)*n，总体来说O(n^2)的时间复杂度 空间复杂度：由于要用额外数组无法避免的O(n)

解法二：优化

上面的解法效率确实是不够的，其实之前做了那么一系列数组的算法题，虽然都是初级合集的但明显我们能明白一个关于数组原地变换的一个点，就是通过交换减少规模 但这一题并不能让我们通过交换来减少一半的规模，因为随机取再与后面的交换虽然能达到一半的复杂度并全员随机打乱，但并不是完全随机。所以我们还是要遍历完整每个进行random，这样做还是有个好处就是不需要arrayList了这样可以将n^2的复杂度降为n

代码如下：

 class Solution {
     private int[] nums;
     private int[] result;
     Random random = new Random();
 ​
     public Solution(int[] nums) {
         this.nums = nums;
         result = nums.clone();
     }
     
     public int[] reset() {
         result = nums;
         nums = nums.clone();
         return result;
     }
     
     public int[] shuffle() {
         for (int i = 0; i < result.length; i++) {
             int index = random.nextInt(result.length - i) + i;
             int temp = result[index];
             result[index] = result[i];
             result[i] = temp;
         }
         return result;
     }
 }

空间复杂度：O(n) 时间复杂度：O(n)

总结

这一题主要需要考虑打乱是一个什么状态，操作逻辑有没有影响到“随机”，关于解法一与二采用了两种方式记录原数组与打乱的过程数组，由于解法一的打乱赋值过程分了两个容器list和result所以才可以简略的这样写一个空数组，每次都是完全的按照阶乘的一个选取情况。解法二为了减少生成list所带来n倍的复杂度，采用交换，这样就需要在打乱数组本身原地进行，如果是在原数组取一对赋值到打乱数组那么就会出现重复。还有一个点是重置方法的，我在解法一直接是返回原数组只能说在当前逻辑上是满足，但最好还是像解法二一样真正的对打乱数组进行还原而不是把原数组返回出去。并且这里有个需要注意的点，我们在数组赋值实际上指向同一个对象，整个时候我们重置了result数组但result数组改变会影响原数组nums也就是我们要把nums指向另一个，也就是nums = nums.clone();