Java solution using Reservoir Sampling


  • 1
    F
    public class Solution {
        private int[] nums;
        private Random random;
    
        public Solution(int[] nums) {
            this.nums = nums;
            random = new Random();
        }
    
        public int pick(int target) {
            int result = -1;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target && random.nextInt(++count) == 0) {
                    result = i;
                }
            }
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.