Java AC hash table solution.


  • 0

    Instead of storing each index of a number in a List<>, I use an object to store the range if the indexes are consecutive. Since the indexes are added in order, we can check whether an index is in a consecutive range by peeking the last one.
    In addition, each range object remembers an accumulated count which can be used to pick an index in order.
    Meanwhile, because the ranges are sorted, we can apply binary search to find a random pick.

    public class Solution {
        class Range{
            int from;
            int to;
            int total;
            Range(int from, int to, int total){
                this.from = from;
                this.to = to;
                this.total = total;
            }
        }
        Map<Integer, List<Range>> map = new HashMap<>();
        Random rnd = new Random();
        public Solution(int[] nums) {
            for (int i=0; i<nums.length; i++){
                int num = nums[i];
                if (! map.containsKey(num) ) map.put(num, new ArrayList<Range>());
                List<Range> list = map.get(num);
                int last = list.size()-1;
                if ( (last >=0 ) && ( list.get(last).to == (i-1)) ) {
                    list.get(last).to = i;
                    list.get(last).total++;
                } else {
                    int total = last < 0 ? 1 : list.get(last).total + 1;
                    list.add( new Range( i, i, total) );
                }
            }
        }
        
        public int pick(int target) {
            List<Range> list = map.get(target);
            int last = list.size()-1;
            int total = list.get(last).total;
            int r = rnd.nextInt(total) + 1;
            int s = 0, e = last+1;
            while ( s < e ) {
                int mid = s + ((e-s)/2);
                if (r > list.get(mid).total ) {
                    s = mid+1;
                } else {
                    e = mid;
                }
            }
            int pre_count = s==0 ? 0 : list.get(s-1).total;
            return list.get(s).from + (r-pre_count) - 1 ;
        }
    }
    

Log in to reply
 

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