友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
384. Shuffle an Array
Shuffle a set of numbers without duplicates.
Example:
// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();
// Resets the array back to its original configuration [1,2,3].
solution.reset();
// Returns the random shuffling of array [1,2,3].
solution.shuffle();又学习了一个算法：Fisher-Yates Algorithm。
参考资料
Shuffle a set of numbers without duplicates.
Example:
// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();
// Resets the array back to its original configuration [1,2,3].
solution.reset();
// Returns the random shuffling of array [1,2,3].
solution.shuffle(); 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
* Runtime: 146 ms, faster than 8.33% of Java online submissions for Shuffle an Array.
*
* Memory Usage: 95.1 MB, less than 6.45% of Java online submissions for Shuffle an Array.
*
* Copy from: https://leetcode.com/problems/shuffle-an-array/solution/[Shuffle an Array - LeetCode]
*/
class Solution {
private int[] origin;
public Solution(int[] nums) {
this.origin = nums;
}
/**
* Resets the array to its original configuration and return it.
*/
public int[] reset() {
return this.origin;
}
/**
* Returns a random shuffling of the array.
*
* Fisher-Yates Algorithm
*/
public int[] shuffle() {
if (Objects.isNull(this.origin)) {
return null;
}
int[] result = this.origin.clone();
ThreadLocalRandom random = ThreadLocalRandom.current();
int length = this.origin.length;
for (int i = 0; i < length; i++) {
int temp = result[i];
int index = random.nextInt(i, length);
result[i] = result[index];
result[index] = temp;
}
return result;
}
}
/**
* Runtime: 90 ms, faster than 39.11% of Java online submissions for Shuffle an Array.
*
* Memory Usage: 50.7 MB, less than 100.00% of Java online submissions for Shuffle an Array.
*/
class SolutionBruteForce {
private int[] origin;
public SolutionBruteForce(int[] nums) {
this.origin = nums;
}
/**
* Resets the array to its original configuration and return it.
*/
public int[] reset() {
return this.origin;
}
/**
* Returns a random shuffling of the array.
*/
public int[] shuffle() {
if (Objects.isNull(this.origin)) {
return null;
}
int[] result = new int[this.origin.length];
ThreadLocalRandom random = ThreadLocalRandom.current();
LinkedHashSet<Integer> index = new LinkedHashSet<>();
while (index.size() < this.origin.length) {
index.add(random.nextInt(this.origin.length));
}
int i = 0;
for (Integer integer : index) {
result[i++] = this.origin[integer];
}
return result;
}
}
private void test() {
int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
Solution solution = new Solution(nums);
int[] reset = solution.reset();
int[] shuffle = solution.shuffle();
}