相同概率获取元素O(n)

    public static void main(String[] args) {
        //随机获取元素为3的下标
        int target = 3;
        Random random = new Random();
        int[] arr = {1, 2, 3, 3, 3, 4, 5};
        int cur = 0;
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            //不为3直接跳过
            if(arr[i] != target){
                continue;
            }
            if (random.nextInt(++cur) == 0) {
                res = i;
            }
        }
        System.out.println(res);
    }

第一次找到这个元素，cur = 1 取随机数 [0,1) 必得0，res = 这个元素下标

第二次找到这个元素，cur = 2 取随机数[0,2），有1/2的概率 ，res = 第二个元素下标

第三次找到这个元素，cur = 3 取随机数[0,3) , 有1/3的概率 ，res = 第三个元素下标

分析：

第一个元素概率：

1 x (1-1/2) x (1-1/3) x ... (1-1/k)

= 1 x 1/2 x 2/3 x ... ( k-1) / k

= 1/k

第二个元素概率：

在第二次找到这个元素的时候，有1/2 的概率是自己

1/2 x (1-1/3) x ... (1-1/k)

= 1/2 x 2/3 x ... (k-1)/k

= 1/k