### 398. Random Pick Index

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.

#### Derive

The probability of the n-th target is 1/n, and the probability of the (n-1)-th target is (n-1)/n * 1/(n-1)=1/n.

#### Solution

Solution 1:

Filter all of the target's index, and random choose one.

class Solution(object):
def __init__(self, nums):
self.nums = nums

def pick(self, target):
try:
import random
return random.choice([index for index, n in enumerate(self.nums) if n == target])
except:
return None


Solution 2:

Use the derivation. Traverse the sequence, and make all of the probability same.

class Solution(object):
def __init__(self, nums):
self.nums = nums

def pick(self, target):
import random
count, choice = 0, None
for index, n in enumerate(self.nums):
if n == target:
if choice is None:
choice = index
count += 1
else:
count += 1
if random.random() * count < 1:
choice = index
return choice


Solution 3:

Sort the sequence, and find the index range of the target. And randomly pick one.

class Solution {
public:
typedef pair<int, int> pp; // <value, index>

static bool comp(const pp& i, const pp& j) { return (i.first < j.first); }

vector<pp> mNums;

Solution(vector<int> nums) {
for(int i = 0; i < nums.size(); i++) {
mNums.push_back(pp({nums[i], i}));
}
sort(mNums.begin(), mNums.end(), comp);
}

int pick(int target) {
pair<vector<pp>::iterator, vector<pp>::iterator> bounds = equal_range(mNums.begin(), mNums.end(), pp({target,0}), comp);
int s = bounds.first - mNums.begin();
int e = bounds.second - mNums.begin();
int r = e - s;
return mNums[s + (rand() % r)].second;
}
};


### 382. Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

#### Solution

The same as 398.

class Solution(object):

def getRandom(self):
import random
count, val = 0, None