Problem: 384. 打乱数组

题目描述

思路

打乱数组的主要算法：

从1 - n每次生成[i ~ n - i]的一个随机数字，再将原数组下标位置为i的元素和该随机数字位置的元素交换

复杂度

打乱数组的主要算法
时间复杂度:

$O(n)$；其中$n$为数组的大小

空间复杂度:

$O(1)$

Code

class Solution {private int[] nums;private Random rand = new Random();public Solution(int[] nums) {this.nums = nums;}public int[] reset() {return nums;}/*** Shuffling algorithm** @return int[]*/public int[] shuffle() {int n = nums.length;int[] copy = Arrays.copyOf(nums, n);for (int i = 0; i < n; ++i) {// Generate a random number in the [i, n-1] rangeint r = i + rand.nextInt(n - i);// Exchange nums[i] and nums[r]swap(copy, i, r);}return copy;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}/*** 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();*/