蓄水池抽样leetcode398,leetcode382

Love The Way You Lie 2023-06-09 10:30 14阅读 0赞

蓄水池抽样的用途  
其实就是为了解决在一个不确定的N个数据中（可能这个N会继续增加），  
但是为了等概率的抽取的一个数，或者抽取k个数

理解：

> https://www.iteye.com/blog/bylijinnan-1468985

代码层面的理解：

> http://www.langdebuqing.com/algorithm%20notebook/%E8%93%84%E6%B0%B4%E6%B1%A0%E6%8A%BD%E6%A0%B7%E7%AE%97%E6%B3%95.html

leetcode 398 是蓄水池抽样的一个特例，为了等概率的抽取一个元素。

class Solution {
        
    
        int[] nums;
        Random r = new Random();
        
        public Solution(int[] nums) {
        
            this.nums = nums;
        }
        
        public int pick(int target) {
        
            
            int c = 0;
            int res = 0;
            for(int i = 0;i<nums.length;i++)
            {
        
                if(nums[i] == target)
                {
        
                    c++;
                    if(r.nextInt(c) == 0)
                        res = i;
                }
                
            }
            return res;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(nums);
     * int param_1 = obj.pick(target);
     */

leetcode 382 也是蓄水池抽样的一个特例，为了等概率的抽取一个元素。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        ListNode head;
        Random r = new Random();
        public Solution(ListNode head) {
        
            this.head = head;
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
        
            
            int res = 0;
            int c = 0;
            
            ListNode node = this.head;
            while(node!=null)
            {
        
                c++;
                if(r.nextInt(c) == 0)
                    res = node.val;
                    
                node = node.next;
            }
            
            return res;
            
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */

蓄水池取k个模型：

public class ReservoirSampling {
        
        public static void main(String[] args) {
        
            Scanner sc=new Scanner(System.in);
            int k=sc.nextInt();
            int n=sc.nextInt();
            int[] data=new int[n];
            for(int i=0;i<n;i++){
        
                data[i]=i;
            }
            int[] sample=reservoirSampling(data,k);
            System.out.println(Arrays.toString(sample));
        }
        public static int[] reservoirSampling(int[] data,int k){
        
            if(data==null) {
        
                return new int[0];
            }
            if(data.length<k){
        
                return new int[0];
            }
            int[] sample=new int[k];
            int n=data.length;
            for(int i=0;i<n;i++){
        
                if(i<k){
        
                    sample[i]=data[i];
                }else{
        
                    int j=new Random().nextInt(i);
                    if(j<k){
        
                        sample[j]=data[i];
                    }
                }
            }
            return sample;
        }
    
    }