FilesExpand file tree

 master

/

RandomPickIndex.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

50 lines (40 loc) · 1.85 KB

 master

/

RandomPickIndex.java

Copy path

Top

File metadata and controls

• Code
• Blame

50 lines (40 loc) · 1.85 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

41

42

43

44

45

46

47

48

49

50

import java.util.Random;

/**

* 注意这里一定要给整个数组遍历完，这样才能保证所有数字的概率是一样的，否则只能保证

* 当前遍历过的数都是等概率的。

*/

/**

* 这道题涉及到reservoir sampling，就是从n个数中随机抽取k个数，要保证每个数都是等概率的。

* 做法是维护一个大小为k的池子，当池子还没装满时，不停的往里装，当池子装满后，就要考虑是用新数替换池子中旧的

* 数，还是丢弃新数。现在的问题是来了一个新数，这个数的编号是x，那么该怎么做呢？

* 我们首先以k / x的概率来决定是否保存新数，即生成一个[0,1)之间的数，如果小于k/x，则保留新数，同时随机

* 替换掉池子中的一个数。如果大于k/x，则丢弃新数。

*/

/**

* 本题是随机抽取一个数，所以是否保留当前数就看random的结果是否小于1，即为0。如果为0，则替换掉。

*/

/**

* 类似的题还有从文件中随机读取一行，如果是流数据中随机取则到当前为止就好了，如果是数组或链表这种固定数据中随机取，

* 则有遍历完才能返回。类似的题目可参考https://leetcode.com/problems/linked-list-random-node/

*/

public class RandomPickIndex {

private Random mRandom;

private int[] mNums;

public RandomPickIndex(int[] nums) {

mRandom = new Random();

mNums = nums;

}

public int pick(int target) {

int count = 0;

int result = -1;

for (int i = 0; i < mNums.length; i++) {

if (mNums[i] == target && mRandom.nextInt(++count) == 0) {

/**

* 这里只是暂时替换掉result，不能返回。result相当于大小为1的池子

*/

result = i;

}

}

return result;

}

}