# Simple JAVA solution

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

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

• 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;
}
}
}
``````

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

• 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?

• @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"?

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

• @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?

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