LeetCode初級(jí)算法--設(shè)計(jì)問(wèn)題01：Shuffle an Array （打亂數(shù)組）

一、引子

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

二、題目

打亂一個(gè)沒(méi)有重復(fù)元素的數(shù)組。

示例:

// 以數(shù)字集合 1, 2 和 3 初始化數(shù)組。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打亂數(shù)組 [1,2,3] 并返回結(jié)果。任何 [1,2,3]的排列返回的概率應(yīng)該相同。
solution.shuffle();

// 重設(shè)數(shù)組到它的初始狀態(tài)[1,2,3]。
solution.reset();

// 隨機(jī)返回?cái)?shù)組[1,2,3]打亂后的結(jié)果。
solution.shuffle();

1、思路

遍歷數(shù)組每個(gè)位置，每次都隨機(jī)生成一個(gè)坐標(biāo)位置，然后交換當(dāng)前位置和隨機(jī)位置的數(shù)字，這樣如果數(shù)組有n個(gè)數(shù)字，那么也隨機(jī)交換了n組位置，從而達(dá)到了洗牌的目的。

2、編程實(shí)現(xiàn)

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()

本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！

審核編輯 黃昊宇