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);
}
Simple JAVA solution

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

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