Weighted Random

题目：给一组id和表示每个id出现概率的数组，概率之和为1.要求随机生成id，使得随机出的id满足之前的概率数组

所给ID： 1, 2, 3
所给概率：0.1， 0.3， 0.6. 
现在我们要随机生成一个ID，这个生成方法要求按照概率来生成。
也就是10% 给出1, 30% 给出2， 60% 给出3.


一个数组
1,4,2,6.....
每次调⽤用一个函数，按照数组里面的数字的大小所形成的概率，返回相应的Index。
比如， 上面的例⼦子就是
1/13 的概率返回0,
4/13的概率返回1

解题方法：
先找cumulative probability［1, 5, 7, 13]， 然后弄个0～13之间的random数字⽐较过去找它的位置就好 
binary search: leetcode的insert position

import java.util.Arrays;
import java.util.Random;


public class WeightedRandom {
	public int weightedRandom(int[] nums) {
		int[] arr = new int[nums.length];
		arr[0] = nums[0];
		for(int i=1; i<nums.length; i++) {
			arr[i] = arr[i-1] + nums[i];
		}
		System.out.println(Arrays.toString(arr));
		
		Random rand = new Random();
		int num = rand.nextInt(arr[nums.length-1]) + 1;
		System.out.println("number selected: " + num);
		
		int left = 0, right = arr.length - 1;
		while(left <= right) {
			int mid = left + (right-left)/2;
			if(arr[mid] == num) {
				return mid;
			} else if(arr[mid] > num) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return left;
		
	}
	
	public static void main(String[] args) {
		WeightedRandom test = new WeightedRandom();
		int[] nums = {1, 4, 2, 6};
		System.out.println("index of this number: " + test.weightedRandom(nums));
	}
}