FilesExpand file tree

 master

/

ShuffleAnArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (34 loc) · 1.1 KB

 master

/

ShuffleAnArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (34 loc) · 1.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

import java.util.Arrays;

import java.util.Random;

public class ShuffleAnArray {

private int[] mNums;

private Random mRandom;

public ShuffleAnArray(int[] nums) {

mNums = nums;

mRandom = new Random();

}

/** Resets the array to its original configuration and return it. */

public int[] reset() {

return mNums;

}

/** Returns a random shuffling of the array. */

/**

* 注意这里生成随机数时的范围是i+1，就是[0,i]

* 我们要确保[0,j]范围内的数在j的概率都是一样的，即1/(j+1)

* 假如生成的随机数是j，则显然概率是1/(j+1)

* 假如随机数不是j，则在[0,j-1]中，swap到j，概率是(1-1/(j+1))*1/j=1/(j+1)

*/

public int[] shuffle() {

int[] array = Arrays.copyOf(mNums, mNums.length);

for (int i = 1; i < array.length; i++) {

int index = mRandom.nextInt(i + 1);

swap(array, i, index);

}

return array;

}

private void swap(int[] arr, int i, int j) {

int t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

}