题目描述：

LeetCode 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.

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);

题目大意：

给定一个可能包含重复元素的整数数组，给定一个目标数，随机输出其下标。你可以假设给定的目标数一定存在于数组中。

注意：

数组长度可能很大。使用较多额外空间的解决方案无法通过系统测试。

解题思路：

利用链表（Linked List）数据结构

初始化：

数组next记录当前下标的下一个下标；

字典head记录目标数target对应链表头部的数组下标

随机选取：

首先找到target对应的数组下标链表的头部，记为head

然后从head开始，通过next数组遍历一遍链表，求出链表长度，记为cnt

接下来随机选取0到cnt之间的数，记为c

最后从head开始，越过c-1个节点，将该节点返回

Python代码：

class Solution(object):

    def __init__(self, nums):
        """
        
        :type nums: List[int]
        :type numsSize: int
        """
        size = len(nums)
        self.next = [0] * (size + 1)
        self.head = collections.defaultdict(int)
        for i, n in enumerate(nums):
            self.next[i + 1] = self.head[n]
            self.head[n] = i + 1

    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        cnt = 0
        idx = self.head[target]
        while idx > 0:
            cnt += 1
            idx = self.next[idx]
        c = int(random.random() * cnt)
        idx = self.head[target]
        for x in range(c):
            idx = self.next[idx]
        return idx - 1

 

本文链接：http://bookshadow.com/weblog/2016/09/11/leetcode-random-pick-index/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码