leetcode Shuffle an Array
Shuffle a set of numbers without duplicates.
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 // 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();
题目地址:leetcode Shuffle an Array
题意:给定一个数组,实现两个接口 reset() 和 shuffle(), 前者为置位返回初始的数组,后者为随机化数组。
思路:用swap,每次从[i,n-1]中随机一个数,和第i个数交换即可。
Python code如下:
1 | class Solution(object): |
当然,上面的代码是每次洗牌从上一次的结果继续进行的,这也符合我们对于洗牌的感觉。
如果每次从初始数组进行洗牌,那么reset数组只需要返回初始数组。。
1 | class Solution(object): |
其他的代码:
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
vector<int> nums;
vector<int> output;
public:
Solution(vector<int> nums) :nums(nums),output(nums) {}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return output = nums;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
int n = output.size();
for (int i = 0; i < n; i++) {
int _id = rand() % (n - i);
swap(output[i], output[i + _id]);
}
return output;
}
};
Java
1 | public class Solution { |
本题是leetcode 384 Shuffle an Array 的题解
更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/