# 0398. Random Pick Index
###### tags: `Leetcode` `FaceBook` `Medium` `Reservoir Sampling`
Link: https://leetcode.com/problems/random-pick-index/
## 思路
因为给的例子是按从小到大的顺序排的，所以一开始以为应该要用binary search，然后左右边界搞了半天，结果发现不是排序过的list

但跟[二分查找详解](https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E8%AF%A6%E8%A7%A3.md)学了一下怎么找左右边界以及如何判断while里面要不要加等号（看出回圈的条件是否对应空区间）

如果初始right = nums.length, 则不加等号，因为这说明搜索区间是[0,nums.length), 最后出回圈的条件是left=right，也就说明答案区间为[left,right)

如果初始right = nums.length-1,则加等号，因为这说明搜索区间是[0,num.length-1], 最后出去的条件是left=right+1

找左边界就代表，即使nums[mid] = target, 还是要让end = mid, 通过不断缩小右边界来找答案
找右边界同理

**正确思路 用hashmap存idx或蓄水池抽样**
[蓄水池抽样讲解](https://zhuanlan.zhihu.com/p/29178293)

**蓄水池抽样是一系列的随机算法，其目的在于从包含 n 个项目的集合 S 中选取 k 个样本，其中 n 为一很大或未知的数量，尤其适用于不能把所有 n 个项目都存放到内存的情况。**

如果要抽k个值，就维持一个size为k的数组
对于前k个数，我们全部保留，对于第i（i>k）个数，我们以 k/i 的概率保留第i个数，并以 1/k 的概率与前面已选择的k个数中的任意一个替换。

## Code
### 蓄水池抽样法 （Reservoir Sampling）

class Solution {
    private int[] arr;
    private int size;
    Random rand;
    
    public Solution(int[] nums) {
        arr = nums;    
        size = nums.length;
        rand = new Random();
    }
    
    public int pick(int target) {
        int cnt = 0;
        int idx = 0;
        for(int i = 0;i < size;i++){
            if(arr[i] == target){
                cnt++;
                if(rand.nextInt(cnt)==0){
                    idx = i;
                }
            }
        }
        return idx;
    }
    
}

### HashMap

class Solution {
    private int[] arr;
    private Map<Integer, List<Integer>> map;
    private int size;
    Random rand = new Random();
    
    public Solution(int[] nums) {
        arr = nums;    
        size = nums.length;
        map = new HashMap<>();
        buildMap();
    }
    
    public int pick(int target) {
        return map.get(target).get(rand.nextInt(map.get(target).size()));
    }
    
    public void buildMap(){
        for(int i = 0;i < arr.length;i++){
            if(map.containsKey(arr[i])){
                map.get(arr[i]).add(i);
            }
            else{
                map.put(arr[i], new ArrayList<Integer>());
                map.get(arr[i]).add(i);
            }
        }
    }
}

### 错误BinarySearch思路

class Solution {
    private int[] arr;
    private int size = 0;
    Random rand = new Random();
    
    public Solution(int[] nums) {
        arr = nums;    
        size = nums.length;
    }
    
    public int pick(int target) {
        int[] range = binarySearch(target);
        // System.out.println(range[0]+" "+range[1]);
        return rand.nextInt(range[1]-range[0])+range[0];
    }
    
    public int[] binarySearch(int target){
        int[] range = new int[2];
        
        int begin = 0;
        int end = size;
        int mid;
        
        while(begin<end){
            mid = (begin+end)/2;
            if(arr[mid]>=target){
                end = mid;
            }
            else{
                begin = mid+1;
            }
        }
        range[0] = begin;
        
        begin = 0;
        end = size;
        
        while(begin<end){
            mid = (begin+end)/2;
            if(arr[mid]<=target){
                begin = mid+1;
            }
            else{
                end = mid;
            }
        }
        range[1] = begin;
        return range;
    }
}