o(1) Memory with Reservoir Sampling, JAVA


  • 2
    D

    Since the question says it focusing on memory, we discard the solution according to Map. And since it has not been sorted, binary search does not work here.

    public int pick(int target) {
            int count = 0, index = -1;
            for(int i = 0; i<n.length; i++){
                if(n[i] == target&&Math.random()*(++count)<1.0) index = i;
            }
            return index;
        }
    

Log in to reply
 

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