LeetCode 384 打乱数组 [Swift]
2019-08-20
题目
以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
打乱数组 [1,2,3] 并返回结果。任何 [1,2,3] 的排列返回的概率应该相同。
solution.shuffle();
重设数组到它的初始状态 [1,2,3]。
solution.reset();
随机返回数组 [1,2,3] 打乱后的结果。
solution.shuffle();
思路
在解题过程中，考虑到本题考查的两个关键点：深浅拷贝、生成的数组应该被随机打乱。
关于第一点，创建一个数组进行深拷贝，reset 返回改数组即可。
关于第二点，最直接的办法是从源数组中每次取出一个元素，加入到目标数组，然后将该元素从源数组中移除，类似从黑盒中取球，结果是随机的，但该方法的时间复杂度是 O(n^2)，乘方复杂度主要来自 n 次 “将元素从源数组中移除”。
下面的算法采用时间复杂度更优的 “洗牌算法”，通过一次遍历，让数组中的元素互相交换，空间和时间复杂度都为 O(n)：
class Solution {
private var rNum : [Int];
private var sNum : [Int];
init(_ nums: [Int]) {
rNum = nums
sNum = [Int]()
for i in nums {
sNum.append(i)
}
}
func reset() -> [Int] {
return rNum
}
func shuffle() -> [Int] {
if sNum.count <= 1 {
return sNum
}
for i in 0...(sNum.count - 1) {
let originIndex = sNum.count - 1 - i;
var swapIndex : Int
if originIndex == 0 {
swapIndex = 0
} else {
swapIndex = Int.random(in: 0...originIndex)
}
let tmp = sNum[originIndex];
sNum[originIndex] = sNum[swapIndex]
sNum[swapIndex] = tmp
}
return sNum
}
}