Question
Formatted question description: https://leetcode.ca/all/384.html
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();
Algorithm
Traverse each position of the array, randomly generate a coordinate position each time, and then exchange the number of the current traverse position and the randomly generated coordinate position.
If the array has n numbers, then we also randomly exchange n sets of positions, thus achieving the purpose of shuffling.
It should be noted here that i + rand()% (res.size()-i)
cannot be written as rand()% res.size()
.
Code
Java
-
import java.util.ArrayList; import java.util.List; import java.util.Random; public class Shuffle_an_Array { // 1. array deep copy // 2. random.nextInt to dynamic list size class Solution { private int[] array; private int[] original; private Random rand = new Random(); private List<Integer> getArrayCopy() { List<Integer> asList = new ArrayList<Integer>(); for (int i = 0; i < array.length; i++) { asList.add(array[i]); } return asList; } public Solution(int[] nums) { array = nums; original = nums.clone(); } public int[] reset() { array = original; original = original.clone(); return array; } public int[] shuffle() { List<Integer> aux = getArrayCopy(); for (int i = 0; i < array.length; i++) { int removeIdx = rand.nextInt(aux.size()); array[i] = aux.get(removeIdx); aux.remove(removeIdx); } return array; } } /** * 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(); */ }
-
// OJ: https://leetcode.com/problems/shuffle-an-array/ // Time: // Solution: O(N) // reset: O(1) // shuffle: O(N) // Space: O(N) class Solution { private: vector<int> nums; public: Solution(vector<int> nums) : nums(nums) {} vector<int> reset() { return nums; } vector<int> shuffle() { vector<int> ans(nums); for (int i = nums.size(); i > 1; --i) { int j = rand() % i; swap(ans[i - 1], ans[j]); } return ans; } };
-
class Solution(object): def __init__(self, nums): """ :type nums: List[int] :type size: int """ self.nums = nums self.reset = lambda: self.nums def shuffle(self): """ Returns a random shuffling of the array. :rtype: List[int] """ nums = self.nums + [] for i in reversed(range(0, len(nums))): idx = random.randrange(0, i + 1) nums[i], nums[idx] = nums[idx], nums[i] return nums # Your Solution object will be instantiated and called as such: # obj = Solution(nums) # param_1 = obj.reset() # param_2 = obj.shuffle()