[LeetCode]384. Shuffle an Array 给数组洗牌

题目地址:(?)

https://leetcode.com/problems/shuffle-an-array/

题目描述:

Shuffle a set of numbers without duplicates.

Example:

题目大意:

不依靠副本,将一系列数字洗牌。

例如:


这题没写出来,其中我遇到了两个问题:

  1. 不依靠副本,那么该如何重置这个数组?(后来发现自己理解错了题意。重置数组必然需要一个载体。)
  2. 如何完成洗牌?可能性如何统一?该交换几次才够洗干净?就连我们平时打扑克牌洗牌的次数都不太一样,该用什么标准去写?
  3. 完成洗牌必定使用随即函数rand( )。那么该怎么用它?

由于理解错了题意,所以迟迟没有动手写。然后我还是查找了答案。

理解了算法之后,我仿照着写了我的答案。


答案地址:http://blog.csdn.net/cuihaolong/article/details/52240535

“(引用)

给定一个数组nums,对其进行洗牌,要求nums中的每个元素都以等概率被移动,并且能够返回初始数组。

总结一下,正如之前所说的那样,必定需要容器给他reset。所以我的担心是多余的。同时,其实洗牌的方法也挺容易理解的。遍历一遍,让每个元素都有变换位置的机会,而新的位置则随机决定,这样的话得到的结果概率确实是相等的。

以后一定要大胆地往class里加自己的私有成员。然后rand( )函数一般是与取模运算 % 号同时出现的。至于等可能性,其实之前那题 [LeetCode]382. Linked List Random Node 链表的随机节点 之中,我其实已经用到了这个rand( )% 某个数字的这个做法。然后这一次的等可能性,思路也可以是,让每个元素都有机会,也是一种等可能性的意思。