leetcode398。乱数インデックス：貯水池のサンプリング
Leetcode398 Random Number Index
n番目のデータが読み取られようとしていると仮定すると、1 / nの確率でデータを残します。それ以外の場合は、最初のn-1データの1つを残します。このようにして、すべてのデータストリームのデータが選択されます。確率は同じです。
特定のコード
class Solution { int[] nums public Solution(int[] nums) { this.nums = nums } public int pick(int target) { Random r = new Random() int index = 0 int n = 0 for(int i = 0i < nums.lengthi++){ if(nums[i] == target){ n++ if(r.nextInt() % n == 0){ index = i } } } return index } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums) * int param_1 = obj.pick(target) */