蓄水池算法

忘是亡心i 2022-05-27 20:36 297阅读 0赞

20180402102546954

  1. //蓄水池算法
  2. public class CollectionA{
  3.      //一个简单的随机函数，决定一件事情做还是不做
  4.     public static int rand(int max)
  5.     {
  6.          return (int)(Math.random()*max)+1;
  7.     }
  8.     //以k/N的概率进袋子
  9.     public static int[]getKNumsRand(int k,int max)
  10.     {
  11.          if(max<1||k<1)
  12.          {
  13.               return null;
  14.          }
  15.          int[]res=new int[Math.min(k,max)];
  16.          for(int i=0;i!=res.length;i++)
  17.          {
  18.                res[i]=i+1; //前k个数直接进袋子
  19.          }
  20.          for(int i=k+1;i<max+1;i++)
  21.          {
  22.               if(rand(i)<=k) //决定i进不进袋子
  23.               {
  24.                     res[rand(k)-1]=i; //i随机替掉袋子中的一个
  25.               }
  26.          }
  27.          return res;
  28.     }
  29.     //打印数组的内容
  30.     public static void printArr(int[]arr)
  31.     {
  32.           for(int i=0;i<arr.length;i++)
  33.           {
  34.                System.out.print(arr[i]+" ");
  35.           }
  36.           System.out.println();
  37.     }
  38.      public static void main(String[]args)
  39.      {
  40.            int[]arr=getKNumsRand(10,10000);
  41.            printArr(arr);
  43.      }
  44. }

20180402102610879

发表评论

表情：
评论列表 （有 0 条评论，297人围观）

还没有评论，来说两句吧...

相关阅读

    相关 蓄水池算法

    先看一道例题(智力题 不用代码实现) 总共有1000个球 和一个空间为十个球的袋子 这一千个球 一个一个的落出 落出但是没进到袋子中的球永久丢失 找不回来了 保证每个球进入袋

    爱被打了一巴掌爱被打了一巴掌/ 0 赞/ 82 阅读

    相关 [算法]蓄水池抽样算法

    问题背景： > 现有一个单链表，要求随机选择链表中的一个节点并返回节点值，并且保持链表中每个节点被选中的概率相同。 刚看到这个问题，很多人肯定会很不屑：这有何难？先求得链表

    Dear 丶Dear 丶/ 0 赞/ 62 阅读