leetcode-384-Shuffle-an-Array

发表于   |  

描述

Shuffle a set of numbers without duplicates.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
// 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();

分析

简单来说，题目的要求就是：对一个不重复元素的数组进行随机的重组。这是一类随机问题的抽象，比如有一个音乐列表，我需要有一个算法生成一个随机的序列，让我可以随机播放这个列表，而且在播放完所有的歌曲前，听到的歌曲是不重复的。解决思路也比较简单，每一次取得一个数组中随机的值，依次放在返回的结果中即可，用伪代码描述就是：

1
2
for i in range(nums.length)
    swap(nums[randint(0, i)], nums[i])

解决方案1(C++)

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
29
30
class Solution {
    vector<int> nums;
    vector<int> result;
public:
    Solution(vector<int> nums): nums(nums), result(nums) {
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        result = nums;
        return result;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int result_size = result.size();
        for(int i = result_size-1; i >= 1; i--) {
            int now = rand() % (i+1);
            swap(result[i], result[i-now]);
        }
        return result;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector<int> param_1 = obj.reset();
 * vector<int> param_2 = obj.shuffle();
 */

解决方案2(Python)

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
29
30
31
32
33
34
35
36
37
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]
        """
        result = self.nums[:]
        result_size = len(result)
        for i in range(result_size):
            now = random.randint(i, result_size-1)
            result[i], result[now] = result[now], result[i]
        return result
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

解决方案3（Golang）

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
29
30
31
32
33
34
35
type Solution struct {
    nums []int
}


func Constructor(nums []int) Solution {
    return Solution{nums: nums}
}


func (this *Solution) Reset() []int {
    return this.nums
}


func (this *Solution) Shuffle() []int {
    numsLen := len(this.nums)
    result := make([]int, numsLen)
    for i := 0; i < numsLen ; i++ {
        result[i] = this.nums[i]
    }
    for i := numsLen-1; i >= 1; i-- {
        now := rand.Intn(i+1)
        result[i], result[now] = result[now], result[i]
    }
    return result
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Reset();
 * param_2 := obj.Shuffle();
 */

相关问题

题目来源