July 25, 2017

LeetCode Digest - Random Pick Series

LeetCode Digest - Random Pick Series

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 __init__(self, head):
        self.head = head

    def getRandom(self):
        import random
        count, val = 0, None
        head = self.head
        while head:
            if val is None:
                val = head.val
                count += 1
            else:
                count += 1
                if random.random() * count < 1:
                    val = head.val
            head = head.next
        return val