加权随机
加权随机
转为前缀和,二分的方式
二分下标对应的结果,则直接返回
class Solution {
int[] prefix;
int sum=0;
Random r=new Random();
public Solution(int[] w) {
//通过前缀和进行加权随机
int n=w.length;
prefix=new int[n];
for(int i=0;i<n;i++){
sum+=w[i];
prefix[i]=sum;
}
}
public int pickIndex() {
//二分加权随机
int target=r.nextInt(sum);
int left=0;int right=prefix.length-1;
while (left < right) {
int mid=left+right>>1;
if(prefix[mid]>target){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
}
将数组随机打散
打乱数组
将所有的元素放入集合,每一次随机从集合获取一个元素,并将该已经获取过的元素删除
class Solution {
//将所有的元素放入集合,每次都随机获取一个元素
int[] origin;int[] nums;
public Solution(int[] nums) {
int n=nums.length;
origin=new int[n];
this.nums=nums;
System.arraycopy(nums,0,origin,0,n);
}
public int[] reset() {
System.arraycopy(origin,0,nums,0,nums.length);
return nums;
}
public int[] shuffle() {
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
list.add(nums[i]);
}
Random r=new Random();
for(int i=0;i<nums.length;i++){
int index=r.nextInt(list.size());
nums[i]=list.remove(index);
}
return nums;
}
}
随机获取元素
方式一,通过集合将所有的元素存储
class Solution {
Random r;
List<Integer> nums=new ArrayList<Integer>();
public Solution(ListNode head) {
ListNode cur=head;
while(cur!=null){
nums.add(cur.val);
cur=cur.next;
}
r=new Random();
}
public int getRandom() {
return nums.get(r.nextInt(nums.size()));
}
}
方式二:抽样法
class Solution {
Random r;
ListNode head;
public Solution(ListNode head) {
this.head=head;
r=new Random();
}
public int getRandom() {
int i=1;int ans=0;
for(ListNode p=head;p!=null;p=p.next){
if(r.nextInt(i)==0){
ans=p.val;
}
i++;
}
return ans;
}
}
在给定圆心和半径的圆内随机生成点
给定区域随机生成点
通过拒绝采样的方式,所有的区域都可以看成规则的矩形,通过Math.random()在[0,1)范围随机生成实数,映射到规则区域,进行随机拒绝采样
class Solution {
double r;
double x,y;
Random rand=new Random();
public Solution(double radius, double x_center, double y_center) {
this.r=r;
this.x=x;
this.y=y;
}
public double[] randPoint() {
//拒绝采样
while(true){
double x0=x-r+rand.random()*r*2;
double y0=y-r+rand.random()*r*2;
//判断
if(Math.sqrt(Math.pow(x0-x,2)+Math.pow(y0-y,2))<=r){
return new double[]{x0,y0};
}
}
}
}
方式二:通过计算分布函数
非重叠矩形中的随机点
非重叠矩形中的随机点
对于多个非规则矩形进行整体随机拒绝采样,可能会出现超时情况
所以应该先随机选择一个采样区域 ;在单个区域上进行随机拒绝采样
随机选择一个矩形的方式,通过加权随机的方式进行随机
利用随机生成的点数在选中的矩形中进行随机选点
class Solution {
int sum=0;
int[] prefix;
Random r=new Random();
int[][] rects;
public Solution(int[][] rects) {
int n=rects.length;
this.rects=rects;
prefix=new int[n];
for (int i=0;i<rects.length;i++) {
sum+=(rects[i][2]-rects[i][0]+1)*(rects[i][3]-rects[i][1]+1);
prefix[i]=sum;
}
}
public int[] pick() {
//随机生成点数
int tot = r.nextInt(sum);
//通过二分tot
int left=0;int right=prefix.length-1;
//通过二分方式找到第一个大于tot前缀和
while(left<right){
int mid=left+right>>1;
if(prefix[mid]>tot){//mid可能作为答案
right=mid;
}else{
left=mid+1;
}
}
//对于第left个矩形
int y=tot-prefix[left]+(rects[left][2]-rects[left][0]+1)*(rects[left][3]-rects[left][1]+1);
int res_x=rects[left][0]+y%(rects[left][2]-rects[left][0]+1);
int res_y=rects[left][1]+y/(rects[left][2]-rects[left][0]+1);
return new int[]{res_x,res_y};
}
}