Simple JAVA solution


  • 0
        public int pick(int target) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i =0;i<input.length;i++)
            {
                if(input[i] == target)
                    list.add(i);
            }
            Random rand = new Random();
            int index =rand.nextInt(list.size());
            return list.get(index);
        }

  • 0
    L

    So, it takes O(N) time for each pick() operation?
    Does this solution pass the OJ?


  • 0
    L

    is list.size very large?

      public int pick(int target) {
        int index = -1;
        int count = 0;
        for(int i=0; i<nums.length; i++){
          if(nums[i]==target){
            count++;
            int r = random.nextInt(count) + 1;
            if(r == count){
              index = i;
            }
          }
        }
    

  • 1

    Yes OJ accepted it. You should not use more extraspace for this problem. O(n) is fine.


  • 0
    L

    I tried one O(1) solution and one O(lgN) solution. Both of which got "Memory Limit Exceeded". I don't understand what is the point of this problem. Is it intended to be solved by iterating the array for each pick() operation? Any other better solutions?


  • 0
    P

    @lzb700m Same here. I tried using unordered_map<int, vector<int>> to store index, MLE. Then I changed the vector to bitmap, still MLE. But this O(n) pick can pass. After reading other's posts, I realize is the point of this problem the "Reservoir sampling algorithm"?


  • 0
    T

    The array is sort or unsort which dont influence the array index?
    Why r == count
    index = i ?
    if never r == count ?
    the index = -1?


  • 0
    T

    @pmdiano
    The array is sort or unsort which dont influence the array index?
    Why r == count
    index = i ?
    if never r == count ?
    the index = -1?


Log in to reply
 

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