384. 打乱数组
给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象int[] reset() 重设数组到它的初始状态并返回int[] shuffle() 返回数组随机打乱后的结果
示例 1：
输入 ["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 <= 50-106 <= nums[i] <= 106nums 中的所有元素都是 唯一的104 次 reset 和 shuffle原站题解
python3 解法, 执行用时: 124 ms, 内存消耗: 18.7 MB, 提交时间: 2022-12-04 11:02:00
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
self.original = nums.copy()
def reset(self) -> List[int]:
self.nums = self.original.copy()
return self.nums
def shuffle(self) -> List[int]:
for i in range(len(self.nums)):
j = random.randrange(i, len(self.nums))
self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
return self.nums
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
golang 解法, 执行用时: 24 ms, 内存消耗: 7.8 MB, 提交时间: 2022-12-04 11:01:35
type Solution struct {
nums, original []int
}
func Constructor(nums []int) Solution {
return Solution{nums, append([]int(nil), nums...)}
}
func (s *Solution) Reset() []int {
copy(s.nums, s.original)
return s.nums
}
func (s *Solution) Shuffle() []int {
n := len(s.nums)
for i := range s.nums {
j := i + rand.Intn(n-i)
s.nums[i], s.nums[j] = s.nums[j], s.nums[i]
}
return s.nums
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.Reset();
* param_2 := obj.Shuffle();
*/
javascript 解法, 执行用时: 152 ms, 内存消耗: 50.9 MB, 提交时间: 2022-12-04 11:01:20
/**
* @param {number[]} nums
*/
var Solution = function(nums) {
this.nums = nums;
this.original = this.nums.slice();
};
/**
* @return {number[]}
*/
Solution.prototype.reset = function() {
this.nums = this.original.slice();
return this.nums;
};
/**
* @return {number[]}
*/
Solution.prototype.shuffle = function() {
for (let i = 0; i < this.nums.length; ++i) {
const j = Math.floor(Math.random() * (this.nums.length - i)) + i;
const temp = this.nums[i];
this.nums[i] = this.nums[j];
this.nums[j] = temp;
}
return this.nums;
};
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/
java 解法, 执行用时: 48 ms, 内存消耗: 47.3 MB, 提交时间: 2022-12-04 11:00:36
class Solution {
int[] nums;
int[] original;
public Solution(int[] nums) {
this.nums = nums;
this.original = new int[nums.length];
System.arraycopy(nums, 0, original, 0, nums.length);
}
public int[] reset() {
System.arraycopy(original, 0, nums, 0, nums.length);
return nums;
}
public int[] shuffle() {
Random random = new Random();
for (int i = 0; i < nums.length; ++i) {
int j = i + random.nextInt(nums.length - i);
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
}
/**
* 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();
*/
java 解法, 执行用时: 51 ms, 内存消耗: 47.1 MB, 提交时间: 2022-12-04 10:59:58
class Solution {
int[] nums;
int[] original;
public Solution(int[] nums) {
this.nums = nums;
this.original = new int[nums.length];
System.arraycopy(nums, 0, original, 0, nums.length);
}
public int[] reset() {
System.arraycopy(original, 0, nums, 0, nums.length);
return nums;
}
public int[] shuffle() {
int[] shuffled = new int[nums.length];
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums.length; ++i) {
list.add(nums[i]);
}
Random random = new Random();
for (int i = 0; i < nums.length; ++i) {
int j = random.nextInt(list.size());
shuffled[i] = list.remove(j);
}
System.arraycopy(shuffled, 0, nums, 0, nums.length);
return nums;
}
}
/**
* 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();
*/
javascript 解法, 执行用时: 168 ms, 内存消耗: 54.2 MB, 提交时间: 2022-12-04 10:59:37
/**
* @param {number[]} nums
*/
var Solution = function(nums) {
this.nums = nums;
this.original = nums.slice();
};
/**
* @return {number[]}
*/
Solution.prototype.reset = function() {
this.nums = this.original.slice();
return this.nums;
};
/**
* @return {number[]}
*/
Solution.prototype.shuffle = function() {
const shuffled = new Array(this.nums.length).fill(0);
const list = [];
this.nums.forEach((num) => list.push(num));
for (let i = 0; i < this.nums.length; ++i) {
const j = Math.random() * list.length;
shuffled[i] = list.splice(j, 1);
}
this.nums = shuffled.slice();
return this.nums;
};
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/
golang 解法, 执行用时: 20 ms, 内存消耗: 7.8 MB, 提交时间: 2022-12-04 10:58:44
type Solution struct {
nums, original []int
}
func Constructor(nums []int) Solution {
return Solution{nums, append([]int(nil), nums...)}
}
func (s *Solution) Reset() []int {
copy(s.nums, s.original)
return s.nums
}
func (s *Solution) Shuffle() []int {
shuffled := make([]int, len(s.nums))
for i := range shuffled {
j := rand.Intn(len(s.nums))
shuffled[i] = s.nums[j]
s.nums = append(s.nums[:j], s.nums[j+1:]...)
}
s.nums = shuffled
return s.nums
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.Reset();
* param_2 := obj.Shuffle();
*/
python3 解法, 执行用时: 116 ms, 内存消耗: 18.9 MB, 提交时间: 2022-12-04 10:58:25
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
self.original = nums.copy()
def reset(self) -> List[int]:
self.nums = self.original.copy()
return self.nums
def shuffle(self) -> List[int]:
shuffled = [0] * len(self.nums)
for i in range(len(self.nums)):
j = random.randrange(len(self.nums))
shuffled[i] = self.nums.pop(j)
self.nums = shuffled
return self.nums
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()