随机数问题——微软面试题

  1. 云栖社区>
  2. 博客列表>
  3. 正文

随机数问题——微软面试题

奈良佳晴子 2018-08-10 15:21:31 浏览1240 评论1

摘要: 之前同学面试微软,问了一个问题:如果给你一列物品,这列物品各自都有一个权重。如果根据权重随机选取物品。权重值越大,选中的概率就越大。 第一想法肯定就是根据权重的大小扩充这个数组。比如数组里有[‘apple’,’cherry’,’banana’],对应的权重是[3,4,1]。

之前同学面试微软,问了一个问题:如果给你一列物品,这列物品各自都有一个权重。如果根据权重随机选取物品。权重值越大,选中的概率就越大。
QQ_20180808145819

第一想法肯定就是根据权重的大小扩充这个数组。比如数组里有[‘apple’,’cherry’,’banana’],对应的权重是[3,4,1]。那么我们把数组扩充成

[‘apple’,’apple’,’apple’,’cherry’,’cherry’,’banana’]

就像这样,然后每个物品选取的概率就是1/(sum(权重))。
但是这个方法有个问题,第一:占用了太多空间。如果权值很大,则需要一个很大数组。

【云栖快讯】阿里云栖开发者沙龙(Java技术专场)火热来袭!快来报名参与吧!  详情请点击

网友评论

1F
赵志腾

在(0,sum(权重)]内根据权重分区间,每个区间代表物品,然后在此范围内取随机数

1721235007744388奈良佳晴子 赞同