LeetCode初級算法--設計問題01：Shuffle an Array （打亂數組）

一、引子

這是由LeetCode官方推出的的經典面試題目清單~
這個模塊對應的是探索的初級算法~旨在幫助入門算法。我們第一遍刷的是leetcode推薦的題目。

二、題目

打亂一個沒有重復元素的數組。

示例:

// 以數字集合 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();

1、思路

遍歷數組每個位置，每次都隨機生成一個坐標位置，然后交換當前位置和隨機位置的數字，這樣如果數組有n個數字，那么也隨機交換了n組位置，從而達到了洗牌的目的。

2、編程實現

python

class Solution(object):

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

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

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        # 方法一：
        # ans = copy.deepcopy(self.data)
        # random.shuffle(ans)
        # return ans
        #方法二
        ans = copy.deepcopy(self.data)
        for i in range(len(ans)):
            j = random.randint(i, len(ans)-1)
            ans[i], ans[j] = ans[j], ans[i]
        return ans


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

本文由博客一文多發平臺 OpenWrite 發布！

審核編輯 黃昊宇