leetcode-打乱数组

点击：题目链接：给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

思路

提取关键字–打乱。顾名思义，我们要像洗牌一样的“洗数组”。 我们利用标准库的随机函数std::shuffle,随机放置元素后返回“打乱”的数组。

代码

class Solution {
public:
    Solution(vector<int>& nums) {
        original = nums;
        this->nums = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return original;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(nums.begin(), nums.end(), g);
        return nums;
    }

private:
    vector<int> original;
    vector<int> nums;
};

细究

shuffle的基本实现原理：取当前值，和之前读取过的其中一个值互换位置，已达到随机的目的。

代码

vector<int> shuffle() {
    for(int i = 0; i<nums.size();i++){
        int randnum = std::rand() % (original.size()-i);   //只和使用过的值互换位置
        std::swap(nums[randnum],nums[i]); 
    }
    return nums;
}