0%

leetcode Shuffle an Array

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
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
class Solution(object):
def __init__(self, nums):
"""
:type nums: List[int]
:type size: int
"""
self.nums = nums
self.output = nums[:]

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
self.output = self.nums[:]
return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
n = len(self.output)
for i in xrange(n):
_id = random.randint(i, n - 1)
self.output[i], self.output[_id] = self.output[_id], self.output[i]
return self.output

当然,上面的代码是每次洗牌从上一次的结果继续进行的,这也符合我们对于洗牌的感觉。

如果每次从初始数组进行洗牌,那么reset数组只需要返回初始数组。。

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
class Solution(object):

def __init__(self, nums):
"""
:type nums: List[int]
:type size: int
"""
self.nums = nums

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
output = self.nums[:]
n = len(output)
for i in xrange(n):
_id = random.randint(i,n-1)
output[i],output[_id] = output[_id],output[i]
return output

 

其他的代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class 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
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
public class Solution {
private int[] nums;
private int[] output;
private Random random;

public Solution(int[] nums) {
this.nums = nums;
this.output = Arrays.copyOf(nums,nums.length);
this.random = new Random();
}

/** Resets the array to its original configuration and return it. */
public int[] reset() {
return this.output = Arrays.copyOf(nums,nums.length);
}

/** Returns a random shuffling of the array. */
public int[] shuffle() {
int n = output.length;
for (int i = 0; i < n; i++) {
int _id = random.nextInt(n-i);
int temp = output[i];
output[i] = output[i+_id];
output[i+_id] = temp;
}
return output;
}
}

 

本题是leetcode 384 Shuffle an Array 的题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~