動機
python有shuffle
Problem
Given an integer array nums
, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Implement the Solution
class:
Solution(int[] nums)
Initializes the object with the integer array nums.int[] reset()
Resets the array to its original configuration and returns it.int[] shuffle()
Returns a random shuffling of the array.
Example 1:
Input[Solution, shuffle, reset, shuffle][[[1, 2, 3]], [], [], []]Output[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]ExplanationSolution solution = new Solution([1, 2, 3]);solution.shuffle(); // Shuffle the array [1,2,3] and return its result. // Any permutation of [1,2,3] must be equally likely to be returned. // Example: return [3, 1, 2]solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]
Constraints:
1 <= nums.length <= 200
-106 <= nums[i] <= 106
- All the elements of
nums
are unique. - At most
5 * 104
calls in total will be made toreset
andshuffle
.
Sol
class Solution:
def __init__(self, nums: List[int]):
self.origin = nums
self.shu = [x for x in nums]
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.origin
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
shuffle(self.shu)
return self.shu
沒shuffle的話
class Solution:
def __init__(self, nums):
self.array = nums
self.original = list(nums)
def reset(self):
self.array = self.original
self.original = list(self.original)
return self.array
def shuffle(self):
for i in range(len(self.array)):
swap_idx = random.randrange(i, len(self.array))
self.array[i], self.array[swap_idx] = self.array[swap_idx], self.array[i]
return self.array