398. Random Pick Index

Question

Solution

思路：重点是如果数据中有多个数target相等，要从这些数中随机取一个，根据例题

假设输入是：

int[] nums = new int[]{1, 2, 3, 3, 3};

int target = 3;

模拟：

1  != target pass

2  != target pass

3  == target pick的概率 nextInt(1)==0的概率 1,返回这个index的概念是1 - 1/3 -1/3 = 1/3

3  == target pick的概率 nextInt(2)==0的概率 1/2, 返回这个index的概率是1/2 * 2/3 = 1/3

3  == target pick的概率 nextInt(3)==0的概率 1/3, 返回这个index的概率是1/3

Java实现：

class Solution {

    private int[] nums;

    private Random random;

    public Solution(int[] nums) {

        this.nums = nums;

        random = new Random();

    }

    public int pick(int target) {

        int index = -1;

        int count = 0;

        for (int i=0; i<nums.length; i++) {

            if (nums[i] == target && random.nextInt(++count) == 0) {

                index = i;

            }

        }

        return index;

    }

}

/**

 * Your Solution object will be instantiated and called as such:

 * Solution obj = new Solution(nums);

 * int param_1 = obj.pick(target);

 */

Reference

https://gitee.com/okokabcd/leetcode

巴特西

398. Random Pick Index - LeetCode

Question

Solution

Reference

最新文章

热门文章