IVN
0%

Random选编

Posted on Edited on In
Symbols count in article: 6.1k Reading time ≈ 6 mins.

Random选编

528. Random Pick with Weight

前缀和数组 + 二分查找

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
class Solution {

    int[] preSum;
    int n;
    int total;
    public Solution(int[] w) {
        n=w.length;
        preSum=new int[n];
        preSum[0]=w[0];
        for (int i = 1; i < n; i++) {
            preSum[i]=preSum[i-1]+w[i];
        }
        total= Arrays.stream(w).sum();	//整个数组求和
    }

    public int pickIndex() {
        int x=(int)(Math.random()*total)+1;
        return binarySearch(x);
    }

    int binarySearch(int target){
        int left=0;
        int right=n;
        while(left<right){
            int mid=left+(right-left)/2;
            if(preSum[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }
}

382. Linked List Random Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode382 {
    class Solution {
        int count;
        ListNode head;
        public Solution(ListNode head) {
            count=0;
            this.head=head;
            ListNode p=head;
            while(p!=null){
                p=p.next;
                count++;
            }
        }

        public int getRandom() {
            int index=(int)(Math.random()*count);	//注意，(int)优先级小于*，必须加括号
            ListNode p=head;
            while(index-->0){
                p=p.next;
            }
            return p.val;
        }
    }
}

法二：reservoir sampling

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247490892&idx=1&sn=c1fe373edc88142cbabd383ef3c0669b

总的样本数量未知，从所有样本中抽取若干个，要求每个样本被抽到的概率相等。

从前往后处理每个样本

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
class Solution {

    Random random;
    ListNode head;
    public Solution(ListNode head) {
        this.head=head;
        this.random=new Random();
    }

    public int getRandom() {
        int res=0;	//也可以初始化为 res=head.val;		孰优孰劣?
        int count=0;
        ListNode p=head;
        while(p!=null){
            count++;
            int ran=random.nextInt(count);  //	当前1/count的概率被选中
            if(ran==0){
                res=p.val;
            }
            p=p.next;
        }

        return res;	//最后一个被选中的数的被选中概率就是1/n
    }
}

398. Random Pick Index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
        Random random;
        Map<Integer, List<Integer>> map;
        public Solution(int[] nums) {
            random=new Random();
            map=new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if(!map.containsKey(nums[i])){
                    map.put(nums[i],new ArrayList<>());
                }
                map.get(nums[i]).add(i);
            }
        }

        public int pick(int target) {
            List<Integer> list = map.get(target);
            int size=list.size();
            return list.get(random.nextInt(size));
        }
}

法二：reservoir sampling

时间换空间，会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

    int[] nums;
    Random random;
    public Solution(int[] nums) {
        this.nums=nums;
        this.random=new Random();
    }

    public int pick(int target) {
        int count=0;
        int res=0;
        for (int i=0; i<nums.length; i++) {
            if(nums[i]==target){
                count++;
                if(random.nextInt(count)==0){
                    res=i;
                }
            }
        }
        return res;
    }
}

497. Random Point in Non-overlapping Rectangles

32/35 直接法错误！居然还能过32个测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    int[][] rects;
    Random random;
    public Solution(int[][] rects) {
        this.rects=rects;
        this.random=new Random();
    }

    public int[] pick() {
        int n=rects.length;
        int i = random.nextInt(n);	//未考虑到各矩形的面积，并不是等概率选
        int x1=rects[i][0];
        int x2=rects[i][2];
        int y1=rects[i][1];
        int y2=rects[i][3];
        int x=(int)(Math.random()*(x2-x1+1))+x1;
        int y=(int)(Math.random()*(y2-y1+1))+y1;
        return new int[]{x,y};
    }
}

蓄水池采样

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
class Solution {

    int[][] rects;
    Random random;
    public Solution(int[][] rects) {
        this.rects=rects;
        this.random=new Random();
    }

    public int[] pick() {
        int sum=0;
        int index=0;
        for (int i=0; i< rects.length; i++) {
            int[] rect=rects[i];
            int area=(rect[2]-rect[0]+1)*(rect[3]-rect[1]+1);
            sum+=area;
            if(random.nextInt(sum)<area){   //[0,sum)   [0,area)
                index=i;
            }
        }
        int[] arr=rects[index];
        int x1=arr[0];
        int y1=arr[1];
        int x2=arr[2];
        int y2=arr[3];
        return new int[]{random.nextInt(x2-x1+1)+x1,random.nextInt(y2-y1+1)+y1};
    }
}

478. Generate Random Point in a Circle

注意：

  1. Math.random(): [0,1)
  2. random().nextInt(x): [0,x)
  3. random().nextDouble(): [0.0d,1.0d)
  4. random().nextFloat(): [0.0f,1.0f]

法一：rejection sampling: 拒绝采样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    double r;
    double x_center;
    double y_center;
    public Solution(double radius, double x_center, double y_center) {
        r=radius;
        this.x_center=x_center;
        this.y_center=y_center;
    }

    public double[] randPoint() {
        while(true){
            double dx=Math.random()*2*r-r;
            double dy=Math.random()*2*r-r;
            if(dx*dx+dy*dy<=r*r){
                return new double[]{x_center+dx,y_center+dy};
            }
        }
    }
}

法二：几何法

随机生成len和angle，利用三角函数计算出dx,dy

注意，随机生成len时不能直接 在[0,r)间random，因为这样不是对每个点等概率的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    Random random;
    double r;
    double x;
    double y;
    public Solution(double radius, double x_center, double y_center) {
        r=radius;
        x=x_center;
        y=y_center;
        random=new Random();
    }

    public double[] randPoint() {
        double len=Math.sqrt(random.nextDouble()*r*r);
        double angle=random.nextDouble()*Math.PI*2;
        double dx=len*Math.cos(angle);
        double dy=len*Math.sin(angle);
        return new double[]{x+dx,y+dy};
    }
}

380. Insert Delete GetRandom O(1)

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
class RandomizedSet {

    List<Integer> list;
    Map<Integer,Integer> keyToIndex;
    Random rand;
    public RandomizedSet() {
        list=new ArrayList<>();
        keyToIndex=new HashMap<>();
        rand=new Random();
    }

    public boolean insert(int val) {
        if(keyToIndex.containsKey(val)){
            return false;
        }
        keyToIndex.put(val,list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if(!keyToIndex.containsKey(val)){
            return false;
        }
        int idx=keyToIndex.get(val);
        //delete list[idx]:
        //swap list[idx] and list[list.size()-1]
        //delete list[list.size()-1]
        int last=list.get(list.size()-1);
        list.set(idx,last);
        list.remove(list.size()-1);
        keyToIndex.put(last,idx);
        keyToIndex.remove(val);
        return true;
    }

    public int getRandom() {
        int idx=0+rand.nextInt(list.size());
        return list.get(idx);
    }
}

why wrong?!

为何每次iterator.next()都返回相同值？

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
class RandomizedSet {

    Set<Integer> set;
    public RandomizedSet() {
        set=new HashSet<>();
    }

    public boolean insert(int val) {
        if(set.contains(val)){
            return false;
        }
        set.add(val);
        return true;
    }

    public boolean remove(int val) {
        if(!set.contains(val)){
            return false;
        }
        set.remove(val);
        return true;
    }

    public int getRandom() {
        return set.iterator().next();
    }
}