384. 打乱数组

难度：中等

题目

打乱一个没有重复元素的数组。

示例：

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

Reference

题解

基本思路： Fisher-Yates 洗牌算法，关键在于实现数组中元素的无放回抽样。

Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了。

Reference

代码如下：

typedef struct {
    int size;
    int *nums;
} Solution;


Solution* solutionCreate(int* nums, int numsSize) {
    Solution *ret = (Solution *)malloc(sizeof(Solution));
    ret->size = numsSize;
    ret->nums = (int *)memcpy(malloc(sizeof(int) * numsSize), nums, sizeof(int) * numsSize);
    return ret;
}

/** Resets the array to its original configuration and return it. */
int* solutionReset(Solution* obj, int* retSize) {
    *retSize = obj->size;
    return obj->nums;
}

/** Returns a random shuffling of the array. */
int* solutionShuffle(Solution* obj, int* retSize) {
    *retSize = obj->size;
    int *ret = (int *)memcpy(malloc(sizeof(int) * obj->size), obj->nums, sizeof(int) * obj->size), i = 0, temp, x, y;
    unsigned int *seed = malloc(sizeof(unsigned int));
    *seed += (unsigned int)seed;
    srand(*seed);
    for (i = 0; i < obj->size; i++)
    {
        x = i;
        y = rand() % (obj->size - i) + i;
        temp = ret[x];
        ret[x] = ret[y];
        ret[y] = temp;
    }
    free(seed);
    return ret;
}

void solutionFree(Solution* obj) {
    free(obj->nums);
    free(obj);
}

/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(nums, numsSize);
 * int* param_1 = solutionReset(obj, retSize);

 * int* param_2 = solutionShuffle(obj, retSize);

 * solutionFree(obj);
*/

评论