Random Pick Index

Problem: https://leetcode.com/problems/random-pick-index/description/

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

The solution uses the same idea as presented few years back on how to retrieve a random line from a file (which btw, this is a technique that sometimes I still use at work, whenever dealing with massive files, which is usually the norm around here), check out the post: https://anothercasualcoder.blogspot.com/2014/09/a-random-line-from-file.html.
What if the input array was sorted? I bet you could do the Pick operation in LogN....
Code is below, cheers, ACC.

public class Solution
{
 private int[] nums = null;
 private Random rd = null;
 public Solution(int[] nums)
 {
  this.nums = nums;
  rd = new Random();
 }

 public int Pick(int target)
 {
  int count = 0;
  int candidate = -1;
  for (int i = 0; i < nums.Length; i++)
   if (nums[i] == target && rd.Next(0, ++count) == 0) candidate = i;

  return candidate;
 }
}