buckets solution.


  • 0
    Y

    The idea is to save the indexes of the numbers with the same value into one bucket.

        private Map<Integer, List<Integer>> index = new HashMap<>();
        private Random r = new Random();
        
        private void addNum(int x, int idx) {
            List<Integer> idxOfx = null;
            if (index.containsKey(x))   idxOfx = index.get(x);
            else {
                idxOfx = new ArrayList<>();
                index.put(x, idxOfx);
            }
            idxOfx.add(idx);
        }
        
        public Solution(int[] nums) {
            for (int i = 0; i < nums.length; ++i) {
                addNum(nums[i], i);
            }    
        }
        
        public int pick(int target) {
            List<Integer> idxOfTarget = index.get(target);
            if (null == idxOfTarget)    return -1;
            int sz = idxOfTarget.size();
            return idxOfTarget.get(r.nextInt(sz));
        }
    

Log in to reply
 

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